Algorithms/DFS

2.7.1 General Graph

개념

DFS는 아직 방문하지 않은 이웃을 따라 깊게 이동하고, 더 이동할 곳이 없으면 이전 위치로 돌아오는 탐색입니다. 재귀 호출이나 스택으로 돌아갈 위치를 관리합니다. 정점과 간선이 주어진 일반 그래프뿐 아니라 격자의 칸, 연산으로 바뀌는 상태도 같은 방식으로 탐색할 수 있습니다.

방문 순서와 방문 표시

각 정점에 연결된 이웃을 확인하고, 아직 방문하지 않은 정점으로 이동합니다. 새 정점에 도착하면 방문 표시를 한 뒤 그 정점의 이웃을 탐색합니다. 이미 방문한 정점으로 이어지는 간선은 건너뜁니다.

같은 그래프에서 깊게 내려가기

BFS 문서와 같은 정점 1010개, 간선 1111개의 무방향 그래프를 사용합니다. 시작점은 11이고, 모든 정점에서 작은 번호의 이웃부터 확인합니다. 여기서 방문 순서는 정점에 처음 방문 표시를 하는 순서입니다.

진한 정점은 방문한 정점이고, 진한 간선은 현재 재귀 호출 경로입니다. 아래의 방문 목록은 처음 발견한 순서, 경로 목록은 아직 끝나지 않은 재귀 호출을 나타냅니다.

11에는 2,3,42,3,4가 연결되어 있습니다. DFS는 먼저 22로 이동한 뒤 11의 다음 이웃을 확인하기 전에 22의 탐색을 진행합니다. 22에서 55, 55에서 99로 내려가므로 처음 네 정점은 1,2,5,91,2,5,9입니다.

1 2 3 4 5 6 7 8 9 10 방문 1 2 5 9 경로 1 2 5 9
▲ [그림 1] 처음 네 정점 방문: 1 → 2 → 5 → 9

99에서는 방문한 55를 건너뛰고 66으로 이동합니다. 66의 이웃 2,92,9는 모두 방문했으므로 더 내려가지 않고 돌아옵니다. 6→9→5→2→16\to9\to5\to2\to1 순서로 재귀 호출이 끝나며, 22의 다른 이웃인 66도 이미 방문했으므로 다시 들어가지 않습니다. 이제 11의 다음 이웃 33을 방문합니다.

1 2 3 4 5 6 7 8 9 10 방문 1 2 5 9 6 3 경로 1 3
▲ [그림 2] 왼쪽 갈래를 마치고 1로 돌아와 3 방문

33부터는 7→10→8→47\to10\to8\to4로 이동합니다. 정점 44는 시작점 11과 직접 연결되어 있지만, DFS는 먼저 선택한 갈래를 끝까지 탐색하므로 이 예에서는 가장 마지막에 발견합니다.

1 2 3 4 5 6 7 8 9 10 방문 1 2 5 9 6 3 7 10 8 4 경로 1 3 7 10 8 4
▲ [그림 3] 정점 4를 마지막에 발견한 DFS

BFS와 방문 순서 비교

탐색처음 네 정점전체 방문 순서
DFS1,2,5,91,2,5,91,2,5,9,6,3,7,10,8,41,2,5,9,6,3,7,10,8,4
BFS1,2,3,41,2,3,41,2,3,4,5,6,7,8,9,101,2,3,4,5,6,7,8,9,10

DFS가 처음 44를 발견한 경로는 1→3→7→10→8→41\to3\to7\to10\to8\to4로 간선 55개를 거칩니다. 하지만 1→41\to4로 바로 이동하면 간선 11개면 충분합니다. DFS의 첫 발견 경로는 이웃을 확인하는 순서에 따라 정해지므로 최소 이동 횟수를 보장하지 않습니다. BFS는 시작점과 가까운 정점부터 방문하므로 44의 거리를 처음부터 11로 구합니다.

방문 표시는 이웃 탐색보다 먼저 합니다. 무방향 간선 1↔21\leftrightarrow2에서 11의 표시가 없다면 22가 다시 11을 새 정점으로 판단할 수 있기 때문입니다. 사이클이 있어도 각 정점을 한 번씩 방문하도록 하면 탐색을 마칠 수 있습니다.

연결 요소

한 번의 DFS는 시작점에서 도달할 수 있는 정점을 모두 방문합니다. 무방향 그래프에서 전체 정점을 살펴보며 아직 방문하지 않은 정점마다 DFS를 시작하면, 시작한 횟수가 연결 요소의 개수입니다.

간선이 (1,2),(2,3),(4,5)(1,2),(2,3),(4,5)이고 정점이 66개라면, 11에서 시작한 DFS는 {1,2,3}\{1,2,3\}을 방문합니다. 다음 미방문 정점 44에서는 {4,5}\{4,5\}를 방문하고, 66은 혼자 하나의 연결 요소를 이룹니다. 연결 요소는 총 33개입니다.

복잡도

정점 수를 NN, 간선 수를 MM이라고 합니다. 인접 리스트로 간선을 저장하고 각 정점을 한 번씩 방문합니다.

연산시간복잡도공간복잡도
탐색O(N+M)O(N+M)O(N+M)O(N+M)

재귀 호출은 탐색 경로가 길어질수록 깊어집니다. 깊은 탐색에서는 재귀 호출 대신 직접 만든 스택에 탐색할 위치를 저장할 수 있습니다.

예제

문제

무방향 그래프의 연결 요소 개수를 구하여라.

입력

첫째 줄에 정점 수 NN과 간선 수 MM이 공백을 사이에 두고 주어진다. 1≤N≤1001\le N\le100; 0≤M≤N(N−1)/20\le M\le N(N-1)/2이다.

다음 MM개 줄에 간선의 양 끝점 a,ba,b가 공백을 사이에 두고 주어진다. 1≤a,b≤N1\le a,b\le N; a≠ba\ne b이다. 중복 간선은 없다.

출력

연결 요소의 개수를 출력한다.

예제 입력

10 11
1 2
1 3
1 4
2 5
2 6
3 7
4 8
5 9
6 9
7 10
8 10

예제 출력

1

예제 코드

C++20

#include <iostream>
#include <vector>

using namespace std;

vector<int> g[101];
bool seen[101];

void dfs(int u) {
    // 다른 정점으로 이동하기 전에 방문을 표시하여 사이클의 재방문 방지
    seen[u] = true;
    for (int v : g[u]) {
        if (!seen[v]) dfs(v);
    }
}

int main() {
    int n, m, i, a, b, cnt;

    cin >> n >> m;
    for (i = 0; i < m; ++i) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    cnt = 0;
    for (i = 1; i <= n; ++i) {
        // 미방문 정점에서 시작한 DFS 하나가 연결 요소 하나를 탐색함
        if (!seen[i]) {
            ++cnt;
            dfs(i);
        }
    }
    cout << cnt << '\n';
}