자료구조 l 알고리즘 썸네일형 리스트형 DFS (깊이우선탐색) DFS(깊이 우선 탐색)알고리즘 문제에서 BFS(너비 우선 탐색)과 더불어 굉장히 많이쓰이는 기법.그래프에서 더 이상 나아갈 길이 보이지 않을 때까지 한 루트를 깊숙히 탐색하는 방법으로더 이상 나아갈 길이 없을 때 이전 노드로 돌아가 끝까지 탐색. 1번 정점에서 출발했을 때 방문 순서는 1-2-4-8-5-6-3-7 이 된다.5번 정점에서 는 더이상 방문할 곳이 없으므로 이전 노드인 8번으로 되돌아가서 다음 후보지인 6번으로 이동한다.이처럼 현재 노드에서 갈 수 있는 지점까지 방문하고 갈 수 없으면 되돌아가는 방식. Memoization을 이용한 Backtracking에응용될 수 있다. 크게 DFS를 구현할 때1. 재귀호출2. 스택두 가지를 이용하여 구현할 수 있다.다음은 위의 그림 예제를 c++로 구현해.. 더보기 이전 1 다음