DFS (깊이 우선 탐색)

관련 문제

문제	난이도	핵심
1260번 — DFS와 BFS	실버 II	DFS/BFS 기본 구현
2667번 — 단지번호붙이기	실버 I	격자 DFS
11724번 — 연결 요소의 개수	실버 II	연결 요소 탐색
1012번 — 유기농 배추	실버 II	격자 DFS
2606번 — 바이러스	실버 III	연결된 노드 수

---

1. 개념

DFS(Depth-First Search, 깊이 우선 탐색)는 한 방향으로 갈 수 있는 끝까지 파고든 뒤, 막히면 되돌아와 다른 방향을 탐색하는 알고리즘이다.

갈 수 있으면 계속 깊이 들어가고, 막히면 되돌아온다.

스택(Stack) 또는 재귀호출로 구현하며, 보통 재귀 구현이 코드가 간결하다.

---

2. 동작 과정

아래 그래프에서 1번 노드부터 DFS 탐색

1 - 2 - 4
|   |
3   5

단계	현재 노드	방문 처리	다음 이동
1	1	✅	2로 이동
2	2	✅	4로 이동
3	4	✅	더 갈 곳 없음 → 되돌아감
4	2	—	5로 이동
5	5	✅	더 갈 곳 없음 → 되돌아감
6	1	—	3으로 이동
7	3	✅	더 갈 곳 없음 → 종료

탐색 순서: 1 → 2 → 4 → 5 → 3

---

3. 핵심 포인트 2가지

visited 배열로 재방문을 막아야 한다

DFS는 재귀로 깊이 들어가기 때문에, 방문 처리를 하지 않으면 무한 루프에 빠진다.

• 노드를 방문하는 순간 visited[node] = true로 표시
• 이미 방문한 노드는 탐색 대상에서 제외

그래프 표현 방식에 따라 구현이 달라진다

표현 방식	특징	적합한 경우
인접 리스트	메모리 효율적	노드/간선이 많을 때
인접 행렬	구현 단순	노드 수가 적을 때
격자 (2차원 배열)	dx/dy 방향 배열 활용	지도/격자 문제

---

4. 코드

인접 리스트 방식

static boolean[] visited;
static List<List<Integer>> graph;

static void dfs(int node) {
    visited[node] = true;                           // 방문 표시

    for (int next : graph.get(node)) {              // 인접 노드 순회
        if (!visited[next]) {                       // 미방문 노드만
            dfs(next);                              // 재귀 호출
        }
    }
}

인접 행렬 방식

static boolean[] visited;
static int[][] graph;
static int N;

static void dfs(int node) {
    visited[node] = true;

    for (int next = 1; next <= N; next++) {
        if (graph[node][next] == 1 && !visited[next]) {
            dfs(next);
        }
    }
}

격자(2차원 배열) 방식

static boolean[][] visited;
static int[][] map;
static int[] dx = {-1, 1, 0, 0};  // 상하좌우
static int[] dy = {0, 0, -1, 1};
static int N, M;

static void dfs(int x, int y) {
    visited[x][y] = true;

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];

        if (nx >= 0 && nx < N && ny >= 0 && ny < M   // 범위 체크
                && !visited[nx][ny] && map[nx][ny] == 1) {
            dfs(nx, ny);
        }
    }
}

---

5. 시간복잡도

그래프 표현	시간복잡도
인접 리스트	O(V + E)
인접 행렬	O(V²)

V = 노드 수, E = 간선 수. 간선이 적을수록 인접 리스트가 유리하다.

---

6. 주의사항

• 재귀 깊이 제한: Java는 기본 스택 크기가 작아 노드가 많으면 StackOverflowError가 발생할 수 있다. 이 경우 스택(Stack) 자료구조로 반복문 구현으로 전환하라.
• visited 초기화: 여러 테스트케이스가 주어지는 문제는 매 케이스마다 visited 배열을 초기화해야 한다.
• 격자 문제 범위 체크: nx, ny가 배열 범위를 벗어나는지 먼저 확인하고, 그 다음 visited와 값을 체크해야 한다. 순서가 바뀌면 ArrayIndexOutOfBoundsException이 발생한다.
• 간선 방향: 양방향 그래프는 graph.get(a).add(b)와 graph.get(b).add(a) 둘 다 추가해야 한다. 단방향은 한쪽만.