109. Depth First Search

그래프 탐색(Graph Traversal)은 트리의 탐색과는 다르다. 서브트리와 같은 개념이 그래프에는 존재하지 않는데다 노드들 사이의 경로도 여러 개 존재할 수 있으므로 트리의 탐색 방법을 그래프에 그대로 적용하는 것은 무리이다. 그래서 그래프는 트리와 다른 탐색 방식을 사용하며, 대표적인 방식은 두 가지가 있다.

---

깊이 우선 탐색(Depth First Search)은 노드를 탐색하고 그 노드와 인접한 노드을 차례로 탐색하는 과정을 재귀적으로 반복하는 탐색 방법이다. 현재 노드에서 탐색할 수 있는 노드를 최대한 탐색하는 방식이라고 생각하면 간단하다. 인접한 노드가 여러 개 있을 때 그 노드들의 탐색 순서에 대한 규칙은 따로 없으며 문제 상황에 맞게 정하면 된다.

아래와 같은 그래프가 존재할 때 노드 $\text{A}$에서 DFS를 시작하면 DFS는 다음과 같이 진행된다.

노드 $\text{A}$를 방문하고, 이어서 인접한 노드 중 아직 방문하지 않은 노드로 이동하는 과정을 반복한다. 어떤 노드를 선택하는지에 따라서 노드의 방문 순서가 달라질 수 있다. 만약 아래와 같이 이동한다면 노드 $\text{H}$, 노드 $\text{B}$, 노드 $\text{E}$, 노드 $\text{D}$, 노드 $\text{F}$를 순서대로 방문한 다음 더 이동할 수 있는 노드가 없어진다.

이동할 수 있는 노드가 없다면 이전에 방문한 노드로 돌아가서 탐색을 계속한다. 노드 $\text{F}$에서 노드 $\text{D}$로 돌아가면 인접한 노드 중 노드 $\text{I}$를 아직 방문하지 않았으므로 노드 $\text{I}$로 이동하고 이어서 노드 $\text{C}$로 이동한다.

다시 이동할 수 있는 노드가 없으므로 노드 $\text{I}$로 되돌아가서 노드 $\text{G}$로 이동한다. 이후 되돌아가는 과정을 반복하면 DFS가 끝난다.

이 경우 노드의 방문 순서는 다음과 같다.

$\text{A H B E D F I C G}$

 

구현은 다음과 같이 할 수 있다. 정점의 수는 $n$, 간선의 수는 $m$ 변수로 나타내며 그래프 문제에서는 $n$과 $m$을 이런 의미로 사용하는 경우가 많으므로 익숙해지는 것이 좋다. 각각의 정점에서 dfs 함수가 한 번씩 실행되고 각각의 간선은 두 번씩 확인하므로 시간복잡도는 $\Theta(n+m)$이다.

#import<bits/stdc++.h>
using namespace std;
int vi[100005]; // vi는 visited의 약자로 사용됨
vector<int>v, e[100005];
void dfs(int node)
{
    if(vi[node])return;
    vi[node] = 1;
    v.push_back(node);
    for(auto &p: e[node])dfs(p);
}
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1); // DFS 시작 정점
}

정점의 방문 여부를 $\text{vi}$라는 배열로 체크한다. 배열 이름을 $\text{visit}$으로 하는 경우도 흔한데, C++의 경우 버전에 따라 어떤 헤더 파일에 이름이 visit인 객체가 이미 정의되었을 수 있으며 이 헤더파일을 인클루드한 상태에서 이름이 visit인 전역 배열을 선언하면 컴파일 에러가 발생하므로 주의해야 한다. 배열을 지역 변수로 선언하면 이런 문제는 발생하지 않지만 배열을 초기화하는 것을 잊지 않아야 한다.

---

DFS를 실행하면 그 결과를 바탕으로 DFS 트리(DFS Tree)^[각주:1]를 만들 수 있는데, 이 트리의 간선들은 DFS 실행 중에 새로 방문한 정점과 이전 정점을 잇는 간선들이다. 위에 나온 그래프의 경우 DFS가 끝났을 때 파란색으로 표시된 간선들과 정점들이 합쳐져서 DFS 트리가 된다. 전체 그래프에는 DFS 트리에 포함되지 않는 간선이 존재할 수 있으며 이 간선들은 대체로 다음과 같이 분류한다.

• 트리 간선(Tree Edge)은 DFS 트리에 포함되는 간선이다.
• 정방향 간선(Forward Edge)은 DFS 트리의 시작 정점을 루트로 간주할 때 조상-자손 관계인 두 정점을 연결하는 간선(무향 그래프인 경우) 또는 조상 정점에서 자손 정점 쪽으로 가는 간선(유향 그래프인 경우)을 의미한다.
• 역방향 간선(Backward Edge)은 유향 그래프에서 DFS 트리의 시작 정점을 루트로 가정할 때 자손 정점에서 조상 정점으로 가는 간선을 말한다. 무향 그래프에서는 정방향 간선과 역방향 간선을 따로 구분하지 않는다.
• 교차 간선(Cross Edge)은 유향 그래프에서 트리 간선, 정방향 간선, 역방향 간선이 아닌 모든 간선을 의미한다. 교차 간선이 연결하는 두 정점은 서로 조상-자손 관계가 아니다. 무향 그래프에는 존재하지 않는다.

DFS 트리와 간선의 분류법은 쉬운 문제들에서는 잘 등장하지 않지만 이후에 나오는 개념(SCC 등)에서 사용되므로 익숙해지면 좋다.

 

[연습문제]

 

BOJ 2606. 바이러스 (Silver III)

그래프에서 컴포넌트의 크기나 개수 등을 구할 때 DFS를 실행하면 간단하게 원하는 값을 구할 수 있다. 정점 $1$에서 DFS를 시작했을 때 방문하는 정점의 개수를 구하면 답이 나온다.

 

BOJ 11724. 연결 요소의 개수 (Silver II)

DFS로 그래프의 컴포넌트의 개수를 구한다.

 

CF 1277E. Two Fairs (1900)

정점 a와 b를 시작 정점으로 해서 DFS를 한 번씩 실행하는데 반대쪽 정점은 없는 것으로 간주해야 한다. 이제 정점 a에서 시작한 DFS에서만 방문한 정점의 수와 정점 b에서 시작한 DFS에서만 방문한 정점의 수를 곱하면 된다.

 

→ solved.ac tag: dfs

---

1. DFS 스패닝 트리(DFS Spanning Tree)라고도 한다. [본문으로]