백준_경로찾기
https://www.acmicpc.net/problem/11403 [ 나의 해결법 ]노드 1을 시작점으로 깊이우선탐색을 한다. 이 때 방문한 노드는 노드1에서 갈 수 있는 노드이므로 인접행렬(배열 adj)에 표시해둔다.시작점을 노드1부터 노드 N까지 반복한다. 그럼 모든 정점에 대해서 경로의 존재여부를 구할 수 있다.문제는 깊이우선탐색(DFS)를 이용했다. DFS를 재귀로 많이 구현하는데, 재귀로 구현했다가 시간 초과가 나서 스택(Stack)으로 구현했다. 어차피 재귀도 스택이므로 방법이 크게 다른건 아니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859..
알고리즘/깊이우선탐색(DFS)
2016. 7. 8. 22:25