DFS

DFS란?

DFS(Depth-First Search, 깊이 우선 탐색) 는 그래프나 트리를 탐색할 때 한 길을
끝까지 파고든 뒤, 막다른 곳에서 되돌아와 다른 길을 탐색하는 방식입니다.

미로에서 한쪽 벽을 손으로 짚고 갈 수 있는 데까지 간 다음, 막히면 갈림길로 돌아와
다른 길을 시도하는 것과 같습니다.

1. 그래프 표현부터

탐색하려면 먼저 그래프를 메모리에 담아야 합니다. 가장 흔한 표현은 인접 리스트
입니다 — 각 정점마다 "이어진 정점들의 목록"을 둡니다.

정점 1 → [2, 3]
정점 2 → [1, 4]
정점 3 → [1]
정점 4 → [2]

간선이 적은 희소 그래프에서는 인접 행렬(\(O(V^2)\) 메모리)보다 인접 리스트
(\(O(V + E)\))가 효율적입니다.

2. DFS의 동작

한 정점에서 출발해:

1. 현재 정점을 방문 표시한다.
2. 이어진 정점 중 아직 방문 안 한 곳으로 깊이 들어간다(재귀).
3. 더 갈 곳이 없으면 되돌아온다.

이 "끝까지 갔다가 되돌아오는" 흐름이 재귀와 완벽히 맞아떨어집니다. 그래서 DFS는
보통 재귀로 구현합니다.

3. 방문 표시가 생명

방문 배열을 안 쓰면 같은 정점을 무한히 오갈 수 있습니다(사이클). 방문하면 즉시
표시하고, 표시된 곳은 다시 안 들어간다 — 이것이 DFS의 정확성과 종료를
보장합니다. 각 정점을 한 번씩만 방문하므로 전체 복잡도는 \(O(V + E)\)입니다.

4. DFS로 푸는 문제들

특히 격자(2차원 배열)에서 "연결된 영역의 크기/개수"를 구하는 flood fill이 가장
자주 나옵니다.

5. DFS vs BFS

둘 다 모든 정점을 \(O(V+E)\)에 방문하지만 성격이 다릅니다.

"최단 거리"가 필요하면 BFS, "갈 수 있나/연결됐나/모든 경로"면 DFS가 자연스럽습니다.

정리

DFS는 한 길을 끝까지 파고들고 막히면 되돌아오는 탐색입니다. 인접 리스트로
그래프를 담고, 방문 표시로 사이클을 막으며, 재귀로 간결하게 구현합니다.
연결 요소·경로·사이클·flood fill의 기본 도구입니다.

DFS를 코드로

재귀 DFS, flood fill, 그리고 깊이가 깊을 때를 위한 반복 DFS를 다룹니다.

1. 그래프 입력과 재귀 DFS

vector<int> adj[100001];      // 인접 리스트
bool visited[100001];

void dfs(int u) {
    visited[u] = true;        // 방문 즉시 표시
    // u 처리
    for (int v : adj[u])
        if (!visited[v])
            dfs(v);           // 안 가본 이웃으로 깊이 들어감
}

int main() {
    // 간선 입력 (무방향이면 양쪽 다)
    // for each edge (a, b): adj[a].push_back(b); adj[b].push_back(a);
    for (int i = 1; i <= n; i++)
        if (!visited[i]) dfs(i);   // 연결 요소마다 한 번씩
}

import sys
sys.setrecursionlimit(300000)     # 깊은 DFS 대비 필수!

adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

for i in range(1, n+1): if not visited[i]: dfs(i)로 모든 정점을 돌면
연결 요소의 개수도 셀 수 있습니다.

2. Flood Fill (격자 DFS)

격자에서 상하좌우로 연결된 영역을 탐색합니다.

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int board[1001][1001];
bool vis[1001][1001];

void fill(int x, int y) {
    vis[x][y] = true;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 격자 밖
        if (vis[nx][ny] || board[nx][ny] == 0) continue;        // 방문/벽
        fill(nx, ny);
    }
}

dx, dy 방향 배열로 네 방향을 깔끔하게 순회하는 것이 표준 관용구입니다.

3. 깊이가 깊으면: 명시적 스택 DFS

정점이 \(10^5\)개 일렬로 이어진 그래프는 재귀 깊이가 너무 깊어 스택 오버플로가
날 수 있습니다(특히 파이썬). 그럴 땐 스택으로 직접 구현합니다.

void dfs(int start) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        // u 처리
        for (int v : adj[u])
            if (!visited[v]) st.push(v);
    }
}

def dfs(start):
    st = [start]
    while st:
        u = st.pop()
        if visited[u]:
            continue
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                st.append(v)

방문 표시 시점이 재귀와 미묘하게 다르니(꺼낼 때 표시), 중복 push를 허용하고
꺼낼 때 거르는 방식으로 짭니다.

4. 흔한 실수

• 방문 표시 누락/지연 — 사이클이 있으면 무한 루프. 방문 즉시 표시.
• 파이썬 재귀 한도 — setrecursionlimit 안 하면 깊은 그래프에서 RecursionError.
• 무방향 그래프 단방향 입력 — adj[a], adj[b] 둘 다 넣어야 함.
• 격자 경계 검사 — 인덱스 범위를 먼저 확인하지 않으면 런타임 에러.
• 연결 요소 빠뜨림 — 시작 정점 하나만 DFS하면 떨어진 덩어리를 놓침.

5. 패턴 알아보기

• "연결된 영역/덩어리 개수·크기" → flood fill DFS.
• "A에서 B로 갈 수 있나" → DFS 도달 가능성.
• "사이클이 있나" → DFS 중 회색 정점 재방문 확인.
• 최단 거리는 DFS가 아니라 BFS — 헷갈리지 마세요.

실전에서 DFS 문제 알아보기

탐색 문제 앞에서 "DFS냐 BFS냐"를 고민하게 됩니다. DFS가 자연스러운 문제의
모양과, 깊이 제한이라는 DFS 특유의 함정을 정리합니다.

1. 출제 신호

• 연결 요소 개수 — "단지 수", "섬의 개수". 모든 정점을 돌며 미방문이면
  새 컴포넌트로 세는 구조라 DFS가 가장 짧게 짜집니다.
• 사이클 존재 판정, "다시 자기 자신으로 돌아올 수 있는가".
• 경로의 존재/모양 — "한 줄로 끝까지 들어갔다가 되돌아오는" 서술.
• 트리에서 서브트리 단위 계산 — 자식의 답을 모아 부모의 답을 만드는
  구조(후위 처리)는 DFS 그 자체입니다.
• 반대로 "최단", "최소 횟수" 가 보이면 DFS가 아니라 BFS입니다. 이 구분이
  이 단원에서 가장 중요한 한 줄입니다.

2. 풀이 결정 절차

1. 그래프를 만듭니다 — 인접 리스트(정점·간선형) 또는 격자 + 방향 배열.
2. 방문 표시 시점을 정합니다 — 함수에 들어가자마자(또는 호출 직전) 표시.
3. 재귀 깊이를 가늠합니다 — 정점이 \(10^5\) 이상이면 한 줄로 늘어선
   그래프에서 깊이가 \(N\)까지 갑니다. 파이썬은 한도 조정 또는 스택 변환,
   C++도 스택 크기를 의식하세요.
4. 컴포넌트 문제라면 바깥 루프(모든 정점에 대해 미방문이면 DFS 시작)를
   잊지 않습니다.

3. 자주 하는 실수

• 무방향 그래프에서 부모로 되돌아가 사이클 오탐. 간선 \((u, v)\)를 양쪽에
  넣었으므로, 사이클 판정 시 "직전에 온 정점"은 제외해야 합니다.

bool dfs(int u, int parent) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (v == parent) continue;          // 왔던 길은 사이클이 아니다
        if (visited[v]) return true;        // 진짜 사이클
        if (dfs(v, u)) return true;
    }
    return false;
}

• 방문 표시를 너무 늦게. 표시 전에 같은 정점이 여러 경로로 호출되면
  지수적으로 느려집니다. 들어가자마자 표시가 원칙입니다.
• 파이썬 재귀 한도. 기본 약 1000이라 \(N = 10^5\) 그래프에서
  RecursionError가 납니다. sys.setrecursionlimit(10**6) 또는 명시적
  스택으로 변환하세요.
• 격자에서 방향 배열 오타. dx, dy 네 방향 중 하나를 빠뜨리거나
  부호가 틀리는 고전적 실수 — 항상 같은 상수 쌍을 복사해 쓰는 자기만의
  템플릿을 만드세요.
• 컴포넌트 세기에서 바깥 루프 누락. 1번 정점에서 한 번만 DFS하면 다른
  컴포넌트를 영영 못 봅니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순입니다. 격자
컴포넌트 세기부터 시작해 인접 리스트 그래프, 사이클·트리 문제로 이어집니다.

같은 문제를 재귀와 명시적 스택 두 가지로 한 번씩 짜 보면 깊이 제한 이슈에
대한 감각이 생깁니다. 3문제 이상 풀어 클리어하면 레이팅의
CLASS 보너스에 반영됩니다.