깊이 우선 탐색(Depth-First Search, DFS)

그래프에서 깊이 우선 탐색(Depth-First Search, DFS)는 그래프를 탐색하는 방법 중 하나다. 이름에서 알 수 있듯이 DFS는 최대한 깊게 들어갔다가 다시 나오는 탐색 방식이다. 정확한 동작 방식은 다음과 같다.

 

1. 시작 정점을 방문하고 '방문함'으로 표시
2. 시작 정점과 연결되어 있는 정점 중 아직 방문하지 않는 정점을 시작 정점으로 놓고 1을 반복
3. 연결되어 있고 방문하지 않은 정점이 없다면 이전 정점으로 돌아가 다시 2를 반복
4. 모든 정점을 방문했으면 탐색을 종료

 

이것을 시각화하면 다음과 같다. 1번 정점을 시작 정점이라고 할 때, 연결되어 있는 정점인 2를 방문하고, 2에서는 5를 방문하고, 다시 돌아와 6, 9... 이런 식으로 방문하기 때문에 총 탐색 순서는 1-2-5-6-9-7-10-3-4-11이 된다.

 

---

DFS의 구현

그래프를 인접 행렬로 표현했을 때는 다음과 같이 구현할 수 있다.

bool adj[MAX][MAX]; // 인접 행렬
bool visited[MAX]; // 방문 기록 배열
int n; // 정점의 수

void dfs(int v) {
    visited[v] = 1;

    for (int i = 1; i <= n; i++) {
        // 연결되어 있고 방문하지 않았다면 방문
        if (adj[v][i] && !visited[i]) dfs(i);
    }
}

최소한 모든 정점에 대해서 한번씩은 dfs(i)를 호출해야 하고, 연결된 정점을 확인하기 위해서 모든 정점을 순회해야 하므로 시간 복잡도는 $O(V^2)$가 된다.

 

인접 리스트로 표현할 경우에는 다음처럼 구현할 수 있다.

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

void dfs(int v) {
    visited[v] = 1;

    for (int i = 0; i < adj[v].size(); i++) {
        int nxt = adj[v][i];
        if (!visited[nxt]) dfs(nxt);
    }
}

모든 정점에 대해 한번씩은 dfs(i)를 호출하고, 재귀로 호출하는 횟수는 간선의 개수와 같기 때문에 시간 복잡도는 $O(V+E)$이다.

---

컴포넌트의 개수 구하기

깊이 우선 탐색의 특성상, 한 정점에서 시작하면 같은 컴포넌트에 속하는 정점들만 방문할 수 있다. 그래프 하나가 여러 개의 컴포넌트로 이루어져 있을 때는 그 수를 어떻게 구할까?

 

모든 정점에 대해 DFS를 하면서 카운트를 해 주면 된다. 다만 이미 방문된 정점은 앞서 세어진 컴포넌트에 속하는 정점이므로 방문하지 않은 새로운 정점에 대해서만 DFS를 돌린다.

vector<int> adj[MAX];
bool visited[MAX];
int n; // 정점의 수

void dfs(int v) {
    visited[v] = 1;
    
    for (int i = 0; i < adj[v].size(); i++) {
        int nxt = adj[v][i];
        if (!visited[nxt]) dfs[nxt];
    }
}

int countComponent() {
    int ret = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) dfs(i), cnt++;
    }
    
    return ret;
}