깊이 우선 탐색 썸네일형 리스트형 [알고리즘] 깊이 우선 탐색(DFS, Depth, First Search) - 컴도리돌이 깊이 우선 탐색 너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색(DFS, depth, first search)은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다. 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다. 시간 복잡도 : O(V+E) DFS는 대체로 시작 정점에서 멀이 있는 정점을 찾을 때 적합하다. DFS는 최단 경로를 보장하지 않는다. DFS에 의해 생성된 검색 트리는 길고 좁은 편이며, 상대적으로 적은 메모리를 필요로 한다. 깊이 우선 탐색 관련 문제 [프로그래머스] [level2] 타.. 더보기 이전 1 다음
