[자료구조] 13-1. 깊이 우선 탐색 알고리즘

깊이 우선 탐색은 연결 성분을 찾으면서 신장 트리를 찾고, 이중/강한 연결 성분도 찾을 수 있기 때문에 중요하다.

그래프에서의 탐색 문제는 버텍스들의 집합에 속한 특정 버텍스 v로부터 시작해, 다른 모든 버텍스를 방문하는 방법에 대해 다룬다.

- 가장 중요한 부분은 이미 방문한 노드는 기록해놓고 다시 방문하지 않도록 하는 것이다. 따라서 visit를 저장하는 배열을 추가적으로 사용한다.

- 어떤 순서로 방문할지 기억하기 위해 스택이나 큐를 사용한다. 스택은 깊이 우선 탐색, 큐는 넓이 우선 탐색으로 다룬다.

깊이 우선 탐색을 DFS라고 부른다. 어떤 버텍스에 대해 수행하려면 dfs(v) 라는 함수를 사용한다. 버텍스에 연결된 버텍스는 w라고 부른다.

if(visit(w)=0)

만약 아직 특정 w에 방문하지 않았다면 그 버텍스를 방문해서 수행하라고 명령한다. 더 이상 방문할 버텍스가 없으면 for 루프가 끝나고 자동으로 종료된다.

깊이 우선 탐색은 코드는 간단하지만 이해하기 가장 힘든 알고리즘 중 하나다. DFS는 버텍스 방문 순서를 스택으로 관리한다. 스택을 쓰는 이유는, dfs 안에서 다시 dfs 함수를 호출하는 재귀 호출을 하기 때문이다. 함수 호출은 시스템 스택에서 관리한다. 

w를 방문하는 순서는 특정한 조건이 없으면 오름차순을 따른다.

어떤 vertex u에 대해 dfs를 하면, visit[u]를 true로 선언하고 u에 연결된 w 중 아직 방문하지 않은 것이 있다면 dfs를 하라고 명령한다.

아래의 dfs(u)를 부르는 함수는 글로벌 함수로 만든다. 모든 버텍스에 대해 false로 초기화를 시키고, 그래프의 모든 버텍스에 대해서 방문하지 않은 버텍스를 dfs하도록 한다.

DFS는 for 루프가 작동한다. for 루프의 연산 시간은 그래프를 어떻게 구현했는가에 따라 달라진다.

- 인접 행렬로 그래프를 구성했을 경우

O(n). 어떤 버텍스 u에 대해 모든 칸들을 다 방문한 다음, adjacentcy matrix가 있느냐 즉, 엣지가 연결되어 있느냐를 체크해야 한다.

- 인접 리스트로 그래프를 구성했을 경우

O(1)~O(n). u에 연결된 버텍스만 확인하면 된다. 상수 개가 연결되어 있다면 O(1), n개가 연결되어 있다면 O(n)이 걸린다.

모든 버텍스에서 for 루프를 수행하는데, 걸리는 시간은 O(n)일수도, O(1)~O(n)일 수도 있다. 굉장히 애매하다. 버텍스의 관점에서 보기 때문에 이렇게 되는 것이다. 따라서, DFS의 시간 복잡도를 측정하는 가장 핵심적인 아이디어는, 버텍스의 관점이 아니라 엣지의 관점에서 보는 것이다.

버텍스 u와 w 사이에 엣지가 연결되어 있다고 생각해보자. u에서 dfs함수를 호출하면 w를 방문할 것이다. 하지만 반대로 수행하면 해당 엣지를 방문하지 않을 것이다. 이미 방문했기 때문이다. 이때, 방문하지 않아도 엣지를 한 번 점검은 해야한다. 따라서 모든 엣지를 두 번씩 방문 또는 점검한다고 볼 수 있다.

따라서, 모든 엣지를 상수 번씩 방문하기 때문에 O(m)이 걸린다. 여기서 m은 엣지의 크기를 의미한다. 하지만 만약 엣지가 없는 그래프라면 어떻게 할까? 버텍스에 대한 for loop만 반복 하므로 버텍스의 수만큼 연산한다. 따라서 O(n)이 걸린다.

이 두 가지 요소를 종합하면, DFS의 시간 복잡도는 버텍스의 수 또는 엣지의 수만큼, 이 중에 더 큰 값만큼 연산이 수행된다.

그림으로 다시 알아보자. 

1. disconnected 그래프(엣지가 없는 그래프)

모든 원소가 왼쪽 그래프처럼 떨어져있다. 엣지의 수 m은 0이지만 시간 복잡도는 O(n)이 걸린다.

2. sparse 그래프

버텍스가 n개이면 엣지의 수 m은 버텍스 수에 비례하는 O(n)이다. 이때 시간복잡도는 O(n)이다.

3. dense 그래프(complete 그래프)

엣지의 수가 버텍스의 수의 제곱이다. 그래서 시간 복잡도는 O(n^2)이다.

DFS의 예를 살펴보자. 이 그래프는 0에서 8까지 모두 8개의 버텍스가 있고 위처럼 연결되어 있다.

이 그래프에 DFS를 수행하려면 먼저 visit 배열을 만들어야 한다. 이 배열은 버텍스가 8개이므로 총 8개의 원소를 가지고 있을 것이다. 아직 연산을 수행하기 전이므로 0으로 초기화되어 있다. 또한, DFS를 수행할 스택을 가지고 있다. 이 스택은 우리가 직접 선언하는 게 아니라, 시스템 스택을 이용한다.

어떤 버텍스를 방문해도 상관없지만, 특별한 말이 없으면 오름차순에 의해 방문해야 하므로 0번부터 수행할 것이다.

그럼 현재 dfs(0)이 호출된 것이다. 맨 처음 하는 일은 0번 버텍스의 visit를 1로 바꾸는 것이다. 지금의 w는 1과 2이다. 그 중 더 작은 숫자인 1을 선택한다.

1을 선택했으므로 dfs(1)을 호출한다. 그러면 0이 스택에 들어간다. 

이제 다시 1번 버텍스의 visit을 1로 바꾼다. 

1번 버텍스에 연결된 3, 4 버텍스 중 3으로 이동한다.

dfs(3)을 부르면 1번이 stack에 들어간다. 우리가 그동안 거쳐온 버텍스들이 스택에 차근차근 들어가있다. dfs를 수행하면 역시 3번 버텍스 visit에 1이 들어간다.

3에 연결된 버텍스는 7뿐만 아니라 1도 있다. 7과 1 중에 방문할 버텍스를 선택해야 하는데, visit을 보니 1은 이미 방문했으므로 자연스럽게 7을 선택하게 된다.

7에 방문하면 stack에 3이 들어가고, 7의 visit은 1로 바뀐다.

7에 연결된 버텍스는 3, 4, 5, 6이 있는데, 3은 이미 방문했으므로 제일 작은 4를 선택한다.

4에 방문하면 stack에 7이 쌓이고, 4의 visit은 1이 된다.

4번에는 1번과 7번 버텍스가 연결되어 있다. 하지만 둘 다 방문한기록이 있으모로 return 4를 하면서 끝난다. 

dfs(4)에서 리턴을 했으므로 스택의 탑에 있는 7을 pop하면서 dfs(7)로 돌아간다. 이제 다시 7에서 방문할 버텍스를 찾는다. 

3, 4, 5, 6 중에 3, 4는 이미 방문했으므로 5를 선택한다.

stack에는 다시 7이 쌓이고, 5의 visit이 1로 바뀐다.

5는 2와 7 중 2를 선택한다.

2의 visit이 바뀌고 stack에 5가 쌓인다.

2는 6을 선택한다.

2가 stack에 쌓이고 6이 visit을 1로 바꾼다. 이제 더 이상 방문할 버텍스가 없으므로 리턴하고 2로 넘어간다. 2도 더 이상 방문할 버텍스가 없으므로 5, 7, 3...쭉 돌아간다. 0도 갈 곳이 없으므로 stack이 empty가 된다. 이것은 곧 모든 버텍스를 방문했다는 뜻이므로 dfs가 끝나게 된다.

과연 버텍스를 몇 번 방문한 것일까? 예를 들어 3의 경우, 부를 때 한 번, 리턴할 때 한 번 총 2번을 방문한다. 7번처럼 2번 이상인 경우도 있지만 모든 버텍스는 최소 두 번 방문한다는 특징이 있다. 최소 두 번 방문한다는 컨셉이 DFS가 BFS에 베해 갖는 장점이다.