16. DFS

DFS

빠른 설명

DFS(Depth First Search, 깊이 우선 탐색)는 한 방향으로 갈 수 있는 만큼 깊게 들어갔다가 되돌아오는 그래프 탐색이다. 재귀 또는 스택으로 구현한다.

언제 쓰는가

• 연결 요소 개수 세기
• 그래프나 트리 순회
• 사이클 탐지
• 백트래킹 구조와 연결되는 문제

시간복잡도

• 인접 리스트 기준: $O(V+E)$

참고자료

• CP-Algorithms - Depth First Search
• Wikipedia - Depth-first search
• GeeksforGeeks - Depth First Search
• 나무위키 - 깊이 우선 탐색

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
vector<vector<int>> graph;
vector<bool> visited;
 
void dfs(int v) {
    visited[v] = true;
    cout << v << ' ';
 
    for (int next : graph[v]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}
 
int main() {
    int n = 5;
    graph.assign(n, {});
    visited.assign(n, false);
 
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2};
 
    dfs(0);
}

Python 코드

graph = [
    [1, 2],
    [0, 3],
    [0, 4],
    [1],
    [2],
]
visited = [False] * len(graph)
 
def dfs(v):
    visited[v] = True
    print(v, end=" ")
 
    for nxt in graph[v]:
        if not visited[nxt]:
            dfs(nxt)
 
dfs(0)