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

[서론]

DFS는 BFS와 더불어 그래프 탐색의 기본적인 알고리즘이다.

기본적인 정의와 동작 원리를 이해하고, 이차원 배열에서의 응용 문제들을 풀어보자.

 

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

■ 개념

 그래프를 탐색할 때, 더 높은 level의 노드를 먼저 방문하여 탐색하는 기법이다.

 Tree에서 Preorder 순회, 백트래킹과 유사한 점을 보인다.

 쉽게 말하자면, 갈 수 있는 한 일단 최대로 깊게 들어가는 방법이라 할 수 있다.

■ 동작 원리

다음과 같은 그래프에서 DFS가 어떻게 작동하는지 살펴보자.

위와 같은 그래프에서 1번 노드를 시작으로 각 노드를 탐색하는 상황을 보자.

(단, 같은 level의 노드가 여러 개 있다면 낮은 숫자를 먼저 방문한다)

DFS는 일단 갈 수 있는 최대한 깊게 들어가는 방법이라고 했다.

1번 노드의 자식 노드는 2, 5, 7 이 있지만 이 중 가장 처음 방문하게 되는 노드인 2번 노드를 방문했을 때,

반드시 2번 노드에 딸린 다른 노드들을 모두 방문한 다음에야 다른 자식 노드를 방문하게 된다.

만약 더 이상 깊게 들어갈 수 있는 노드가 없다면, 이전 노드로 되돌아간다.

 

[전체 탐색 과정]

DFS 전체 탐색 과정

 - 1번 노드를 처음 방문한 이후, 더 깊이 들어갈 수 있는 노드는 2, 5, 7번 노드가 있다. 낮은 숫자를 우선 방문하므로 다음엔 2를 방문한다.

 - 2번 노드를 방문한 이후 더 깊이 들어갈 수 있는 노드는 3번 노드가 있다. 그렇기에 다음에 방문하는 노드는 3이다.

 - 3번 노드를 방문한 이후 더 깊이 들어갈 수 있는 노드는 4, 6번 노드가 있다. 낮은 숫자를 우선 방문하므로 다음엔 4를 방문한다.

 - 4번 노드를 방문한 이후에는 더 이상 깊이 들어갈 노드가 없으므로, 3번 노드를 방문했던 상태로 돌아간다.

 - 다시 3번 노드를 보고 있는 상태에서, 4번 노드는 이미 방문했으므로 다음 깊게 들어갈 6번을 방문한다.

 - 6번 노드에서 더 이상 깊게 들어갈 노드가 없으므로, 3번 노드를 방문했던 상태로 돌아간다.

 - 3번 노드에서 이제 더 이상 깊이 들어갈 노드가 없으므로 2번 노드로 돌아가고, 마찬가지로 1번 노드로 다시 돌아간다.

 - 1번 노드에서 더 깊이 들어갈 수 있으며, 아직 방문하지 않은 노드인 5번 노드를 방문한다.

...

■ 구현

갈 수 있는 한 최대한 들어갔다가 막히면 이전 상태로 되돌아간다는 점에서 재귀호출, 스택 구조를 통해 구현한다.

이 게시물에서는 재귀호출을 통해 구현하였다.

(개인적으로는 재귀호출을 통해 구현하는 것이 더 직관적이고 코드가 깔끔한 것 같다.)

[예제 그래프를 탐색하는 코드]

#include <iostream>
#include <vector>
 
using namespace std;
vector<int> adj[9];
bool visit[9];
 
void dfs(int n, int lv) {
    //번호가 n인 노드를 기준으로 한다.
    //현재 노드 방문 여부 기록
    visit[n] = true;
 
    //현재 노드의 번호와 level을 출력
    printf("%d (level : %d)\n", n, lv);
 
    //자신의 인접 리스트를 통해, 연결된 모든 자식을 순서대로 방문
    //이미 방문했던 노드인지 확인해, 갔던 노드를 다시 방문하지 않도록 한다.
    //연결된 자식 노드에서 이 함수가 재귀호출되어 실행되면, 
    //다시 자식 노드 기준으로 연결된 모든 자식을 순서대로 방문할 것이다.
    for (int i = 0; i < adj[n].size(); i++) 
        if(!visit[adj[n][i]]) dfs(adj[n][i], lv + 1);
}
 
void init() {
    adj[1].push_back(2);
    adj[1].push_back(5);
    adj[1].push_back(7);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[3].push_back(6);
    adj[7].push_back(8);
}
 
int main() {
    init();
    printf("[방문 순서]\n");
    dfs(1, 1);
 
    return 0;
}

 노드의 방문 여부를 나타내는 visit 배열을 이용해, 반드시 재귀호출 전에 해당 노드를 방문했는지 확인해주자.

[결과]

방문 순서와 각 노드의 level

 

■ 이차원 배열에서의 DFS

DFS를 응용한 문제는 대부분 이차원 배열에서의 '칸'을 중심으로 나오는 경우가 많다. 다음과 같은 판을 보자.

(3, 3)에서 출발해 이차원 배열의 모든 칸을 탐색하려 한다.

방향을 나타내는 dir 은 북-동-남-서 순서대로 0-1-2-3으로 두었다.

이는 곧, 탐색 방향의 우선도를 북>동>남>서 순으로 높게 잡겠다는 의미와도 같다.

이차원 배열에서는 벽 등으로 완전히 막혀 있는 경우가 아닌 이상 모든 칸이 서로 연결되어 있는 그래프와 같다.

위와 같은 판에서 각 칸을 탐색하는 순서는 다음과 같다.

 

1. 각 칸에서 북-동-남-서 순으로 갈 수 있는 칸이 있는지 살펴본다.

2. 만약 갈 수 있는 칸이라면, 그 칸으로 이동해 1의 과정을 반복한다.

3. 만약 모든 칸이 갈 수 없거나 이미 방문한 칸이라면, 이전에 왔던 칸으로 돌아가 1을 반복한다.

다른 모든 칸을 탐색하는 순서

 

만약 문제에서 벽 등으로 특정 칸들이 완전히 차단되어 있다면, 그 차단된 칸들은 출발점과 연결되어 있지 않으므로

dfs에서 탐색되지 않는다.

이러한 점에서 이차원 배열 Board 에서 특정 그룹으로 칸들을 묶는 경우에 주로 사용된다.

벽 등으로 특정 칸들이 막혀 있는 경우, dfs 탐색을 통해 노란색 영역만 묶을 수 있다.

 

[이차원 배열에서의 DFS 응용 문제]

BOJ2573_빙산 : www.acmicpc.net/problem/2573

BOJ11559_뿌요뿌요 : www.acmicpc.net/problem/11559