DFS (Depth-First Search), DFS, depth-first search, 깊이 우선 탐색, depth-first
정의
깊이 우선 탐색 (Depth-First Search, DFS) 는 그래프 G=(V, E) 에서 갈 수 있는 만큼 깊이 들어가다가 막히면 백트래킹하는 알고리즘. 스택 (LIFO) 또는 재귀 로 구현.
문제 풀이에서 사이클 탐지, 위상 정렬, SCC, articulation point 등의 기초 블록.
문제 상황과 동기
“정점 s 에서 도달 가능한 모든 정점을 방문하되, 방문 시각 (in-time) 과 완료 시각 (out-time) 을 기록하라.”
BFS: 최단 거리는 구하지만 in/out-time 개념 없음.
DFS: 각 정점의 발견 시각 과 종료 시각 을 기록. 이 시각 정보로 back edge, cross edge, tree edge 판별 → 사이클 / 위상 정렬.
핵심 통찰: 스택 LIFO 순서 = 재귀 호출 순서 = 백트래킹 자동.
시각화
핵심 아이디어
in-time / out-time 패턴
time = 0DFS_VISIT(u): time++ in[u] = time visited[u] = true for v in adj[u]: if not visited[v]: parent[v] = u DFS_VISIT(v) time++ out[u] = time
invariant:
정점 u 의 subtree 는 [in[u], out[u]] 구간에 포함.
v 가 u 의 자손 ⇔ in[u] < in[v] < out[v] < out[u].
back edge (v → ancestor) 존재 ⇔ 사이클 존재.
알고리즘
DFS(G): visited ← false[|V|] time ← 0 for u in V: if not visited[u]: DFS_VISIT(u)DFS_VISIT(u): time++ in[u] = time visited[u] = true for v in G.adj[u]: if not visited[v]: parent[v] = u DFS_VISIT(v) else if v is not parent[u] and in[v] < in[u]: # back edge, 사이클 존재 time++ out[u] = time
구현
// DFS 재귀 구현, in/out time 기록#include <bits/stdc++.h>using namespace std;vector<int> adj[100005];bool visited[100005];int in_time[100005], out_time[100005];int timer = 0;void dfs(int u) { visited[u] = true; in_time[u] = ++timer; cout << "visit " << u << " (in=" << in_time[u] << ")\n"; for (int v : adj[u]) { if (!visited[v]) dfs(v); } out_time[u] = ++timer; cout << "finish " << u << " (out=" << out_time[u] << ")\n";}int main() { int n, m, s; cin >> n >> m >> s; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(s);}
# 재귀 DFS, in/out timeimport syssys.setrecursionlimit(200000)input = sys.stdin.readlinen, m, s = map(int, input().split())adj = [[] for _ in range(n + 1)]for _ in range(m): u, v = map(int, input().split()) adj[u].append(v) adj[v].append(u)visited = [False] * (n + 1)in_time = [0] * (n + 1)out_time = [0] * (n + 1)timer = 0def dfs(u): global timer visited[u] = True timer += 1 in_time[u] = timer print(f"visit {u} (in={in_time[u]})") for v in adj[u]: if not visited[v]: dfs(v) timer += 1 out_time[u] = timer print(f"finish {u} (out={out_time[u]})")dfs(s)
// 재귀 DFS, in/out time 기록import java.util.*;import java.io.*;public class Main { static List<Integer>[] adj; static boolean[] visited; static int[] inTime, outTime; static int timer = 0; static void dfs(int u) { visited[u] = true; inTime[u] = ++timer; System.out.println("visit " + u + " (in=" + inTime[u] + ")"); for (int v : adj[u]) { if (!visited[v]) dfs(v); } outTime[u] = ++timer; System.out.println("finish " + u + " (out=" + outTime[u] + ")"); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int s = Integer.parseInt(st.nextToken()); adj = new ArrayList[n + 1]; for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>(); visited = new boolean[n + 1]; inTime = new int[n + 1]; outTime = new int[n + 1]; for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); adj[u].add(v); adj[v].add(u); } dfs(s); }}
💬 댓글