DFS · Depth-first search
깊이 우선 탐색
한 갈래를 끝까지 보고 되돌아와요
A에서 연결된 점을 깊이 우선으로 방문해요
지금 보는 점—
방문한 점0 / 6
현재 위치비교 대상확인한 값
예제 코드
C++
<vector> <functional>std::vector<int> dfs( const std::vector<std::vector<int>>& graph, int start) { std::vector<bool> visited(graph.size(), false); std::vector<int> order; std::function<void(int)> visit = [&](int current) { visited[current] = true; order.push_back(current); for (int neighbor : graph[current]) { if (!visited[neighbor]) visit(neighbor); } return; }; visit(start); return order;}Python
def dfs(graph, start): visited = set() order = [] def visit(current): visited.add(current) order.append(current) for neighbor in graph[current]: if neighbor not in visited: visit(neighbor) return visit(start) return order예제의 A~F는 코드에서 0~5번이에요. graph에는 각 번호의 이웃을 순서대로 담아요.
시작하기
한 갈래를 깊게 따라가요
A에서 시작해요. 다음 점으로 들어갔다가, 갈 곳이 없으면 이전 호출로 돌아와요.
사용 조건
연결된 점을 방문하거나, 탐색 중 들어간 경로와 돌아오는 과정을 관리할 때 사용해요. 이 예제는 재귀 호출로 방문 순서를 기록해요.
먼저 알아두면 좋아요
함수와 재귀 호출을 알고 시작해요. 재귀는 함수가 자기 자신을 호출하는 것이며, 돌아오면 이전 호출의 남은 일을 이어가요.
동작 원리
현재 점에 방문 표시를 남겨요. 아직 방문하지 않은 이웃을 만나면 그 점을 처리하는 함수를 호출해요.
그 호출이 끝나면 원래 점으로 돌아와 남은 이웃을 확인해요. 예제의 방문 순서는 인접 리스트의 순서에 따라 달라질 수 있어요.
- 시간
- O(V + E) · 인접 리스트를 기준으로 해요
- 추가 공간
- O(V) · 방문 표시와 호출 스택을 사용해요
주의할 점
- 방문 표시가 없으면 양방향 연결이나 사이클에서 같은 점을 끝없이 다시 호출할 수 있어요.
- DFS의 방문 순서를 최단거리로 해석하지 않아요. 아주 깊은 재귀는 호출 스택 한계도 고려해요.