[Graph] 그래프의 탐색 - 깊이 우선 탐색 (DFS, Depth-First Search)

DFS (출처 - wikipedia)

 

 

알고리즘 문제에서 가장 큰 비중을 차지하는 유형 중 하나가 바로 그래프 탐색 문제다.

어떤 형태의 코딩 테스트, 알고리즘 시험에서든 가장 쉽게 만날 수 있는 문제 유형이기도 하고 여러 문제가 출제되는 형식이라면 반드시 한문제 이상 포함된다고 할 수 있을 정도다.

그래프 탐색 알고리즘은 필수 중 필수이기 때문에 반드시 익숙해져야 한다.

 

 

---

 

 

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

DFS는 대표적인 그래프 탐색 알고리즘 중 하나다.
직관적인 이름 그대로 깊이를 따라서 탐색해나가는 방법으로 너비 우선 탐색(BFS)과 대조되는 특징을 가진다.
BFS의 경우 동시에 여러 갈래의 길을 뻗어나가듯 탐색한다면 DFS는 일반적으로 미로찾기를 해나갈 때와 같이 분기점에서 하나의 길을 선택하고 그 길을 따라서 갈 수 있는 끝까지 가보는 탐색 방법이다.
이렇게 한 경로로 끝까지 탐색해갔다가 되돌아 오는 방식을 백트래킹(Backtracking) 이라고 부르기도 한다.

 

이러한 탐색 방식 때문에 모든 노드를 방문해야 할 경우 DFS를 많이 사용한다.
특정 노드에서 다른 특정 노드로 갈 수 있는지 확인하는 것 과 같은 케이스가 가장 대표적인 사용 예다.
최단 경로를 구하는 방법으로는 많이 활용되지 않는다.

 

대놓고 그래프 탐색을 요하는 문제에서도 당연히 활용되지만 N개의 선택지 중 M개를 고르고 조합하는 등 경우의 수를 모두 따져봐야 하는 상황에도 활용될 수 있다.

 

 

---

 

 

탐색 과정

탐색 과정은 그림을 이용하면 아주 쉽게 이해할 수 있다.
사람이 손으로 미로 길을 찾아나가는 방식과 유사하다.

일단 한 경로로 끝까지 가보고 다시 분기점으로 돌아가 다시 또 끝까지 탐색해나가는 형태다.

 

 

DFS의 탐색 과정 (출처 - wikipedia), 사람은 보통 미로를 DFS로 푼다

 

 

---

 

시간 복잡도

 

그래프의 표현 방법에 따라서 시간 복잡도가 달라진다.
그래프는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 표현할 수 있는데 시간 복잡도는 각각 O(V^2), O(V+E)가 된다. (V : 정점의 수, E : 간선의 수)

 

 

방향과 가중치가 없는 그래프의 인접 행렬 표현

 

인접행렬로 그래프를 표현하게되면 특정 노드에서 인접한 노드를 탐색하기 위해서 전체 노드 수 V 만큼 배열을 확인해야 한다.
즉 DFS 함수 내에서 V번 인접행렬을 참조하고 DFS가 호출되게 된다.
호출되는 DFS 내에서도 또 마찬가지로 V번 인접행렬을 참조하고 DFS가 호출되어야 하기 때문에 시간복잡도는 O(V^2)이 된다.

 

 

방향과 가중치가 없는 그래프의 인접리스트 표현

 

인접 리스트로 표현하게되면 한번의 DFS 함수 내에서 참조하는 인접한 노드의 수는 간선의 수 E가된다.
따라서 DFS를 최대 모든 노드의 수인 V만큼 탐색하되 각 노드에서의 탐색은 간선의 수인 E만큼 이므로 시간복잡도는 O(V+E)가 된다.

 

 

---

 

 

DFS의 특징

 

1. 방문 기록

탐색과정에서 이미 방문한 노드는 반드시 방문 여부를 기록해두어야 한다.

사실 DFS 뿐만 아니라 BFS 등 다른 그래프 탐색 알고리즘에서도 방문 여부를 기록하고 체크해야 한다.

 

방문 기록을 확인하지 않는다면 마치 미로찾기를 할 때 어느길을 따라서 왔는지 그리지 않고 찾아가는 것과 같이 왔던 길을 다시 탐색하면서 무한 루프에 빠질 수 있다.
순서대로 길을 따라가는 그래프 탐색이 아니라 순열이나 조합을 구하기 위해 DFS를 사용한다면 이 방문 기록을 교묘하게 이용해 원하는 규칙에 따라서 선택하도록 할 수 있다.

 

 

2. 경로 정보를 알 수 있다.

 

한가지 경로를 따라서 끝까지 탐색해보는 방식이기 때문에 항상 지나온 경로 정보를 가지고 있다고 할 수 있다.

어떤 값을 누적하면서 경로를 끝까지 탐색해보거나 경로의 특징을 알아야 한다면 DFS를 이용해야 한다.

 

예를 들어 BOJ 4803 트리 문제나 BOJ 2668 숫자고르기 문제와 같이 특정 경로를 따라갈 때 그래프 내에서 사이클이 존재하는지 확인해야 한다면 어느 노드들을 지나왔는지 알 수 있는 DFS를 활용할 수 있다.
또는 BOJ 1987 알파벳 문제와 같이 경로를 탐색하면서 같은 값을 갖는 노드가 중복되지 않도록 탐색해야하는 문제에서도 활용할 수 있다.

 

그래프 형태를 문제에서 제시하고 있지 않아도 N개의 원소 중 M개를 골라 순열이나 조합을 만드는 형태의 문제에서도 DFS를 활용할 수 있다.
M번의 선택 중에서 각각 한번의 선택 기회를 마치 그래프의 노드에서 다른 노드를 탐색하는 과정으로 묘사하고, 각 선택 차수를 그래프의 level로 여길 수 있다.
이렇게 순열이나 조합과정을 그래프로 모델링해보면 DFS로 한개의 원소씩 선택해나가면서 지금까지 선택한 원소들은 경로가 된다.

 

체스판에 N개의 퀸을 놓을 수 있는지 모든 경우의 수를 따져봐야 하는 BOJ 9663 N-Queen 문제도 어느 자리에 Queen을 놓을지 선택을 하고 직전까지 놓은 퀸의 자리를 경로로 활용하는 백트래킹 문제다.

 

 

---

 

 

구현 방식

 

1. Stack을 이용하는 방식

 

Stack은 가장 먼저 넣은 원소가 가장 마지막에 꺼내지는 FILO(First In Last Out)혹은 LIFO(Last In First Out) 자료구조다.
따라서 일단 한 경로를 따라 끝까지 탐색해보고 더이상 갈 곳이 없다면 하나씩 앞으로 돌아가 다시 탐색해나가는 DFS에서 활용하기 좋은 자료구조이기도 하다.

 

 

실제 Stack으로 DFS를 구현하면 이렇게 가장 마지막에 넣은 인접노드부터 탐색한다

 

스택에 넣는 요소는 바로 다음에 탐색할 노드들이다.

특정 노드를 기준으로 인접한 모든 노드는 스택에 쌓는다.
이제 스택의 가장 top에 위치한, 마지막에 넣은 요소를 꺼내면 방금 지나온 바로 앞 노드에서 넣은 노드 중 하나가 된다.

 

이렇게 매 노드 방문시 인접한 노드들을 스택에 넣고 가장 마지막에 넣은 노드를 꺼내 그 노드에 연결된 인접노드를 스택에 더 위로 쌓아나가면 항상 마지막에 탐색한 노드의 인접 노드를 꺼내면서 한 경로를 끝까지 따라가는 형태가 된다.
더이상 탐색할 수 있는 인접노드가 없을 때 비로소 앞서 넣었던 노드를 꺼내 탐색할 수 있게된다.


실제 코드로 구현해보면 마치 BFS 함수를 그대로 가져와 Queue 대신 Stack을 활용하는 것과 유사한 모습이된다.
앞서 언급했듯 Stack과 Queue의 특성의 차이로 깊이를 우선으로 탐색할지 너비를 우선으로 탐색할지가 결정된다.

 

 

void DFS(int start) {
    stack<int> s;
    int visit[V];
    
    s.push(start);
    visit[start] = 1;
    
    while (!s.empty()) {
    	int curr = s.top();
        s.pop();
        
        for (int i = 0; i < adj[curr].size; i++) {
        	int next = adj[curr][i];
            if (visit[next] > 0) continue;
            
            s.push(next);
            visit[next] = 1;
        }
    }
}

 

 

단순히 그래프 전체를 탐색시키는 코드는 간단하다.
여기에서 주의할 점은 그래프를 무한히 탐색하지 않도록 중복 방문에 대한 처리를 해줘야 한다는 점이다.
이부분은 DFS 뿐만 아니라 다른 어떤 방식의 탐색에서도 주의해야 한다.

DFS는 경로 정보를 알수 있는 특징이 있다고 했는데 Stack을 이용할 때에는 이 정보도 함께 Stack에 push하여 이용할 수 있다.
예를 들어 특정 노드 A에서 B까지 가는 길을 탐색하는데 최소 몇개 이상 노드를 거쳐가야 한다는 조건이 있다면 Stack에 몇개의 노드를 지나왔는지 함께 저장해 이용할 수 있다.
이같은 방법은 DFS를 이용해 순열이나 조합을 만들 때에도 활용할 수 있다.

 

 

// start 부터 end까지 N개의 노드 이상 지나서 갈 수 있는 경우를 세어보자
int DFS(int start, int end) {
    stack<pair<int, int>> s;
    int visit[V], path_cnt = 0;
    
    s.push(start, 0);
    visit[start] = 1;
    
    while (!s.empty()) {
    	int curr = s.top().first;
        int curr_cnt = s.top().second;
        s.pop();
        
        if (curr == end) {
        	if (curr_cnt >= N)
            	path_cnt++;
        }        
        
        for (int i = 0; i < adj[curr].size; i++) {
        	int next = adj[curr][i];
            if (visit[next] > 0) continue;
            
            s.push(make_pair(next, curr_cnt++);
            visit[next] = 1;
        }
    }
    
    return path_cnt;
}

 

대부분 DFS는 스택을 이용하기 보다는 다음에 설명할 재귀함수를 이용하는 방식을 많이 사용하지만 재귀 함수 구현에 익숙하지 않다면 스택을 이용해도 된다.

 

2. 재귀함수를 이용하는 방식

 

함수를 재귀적으로 호출하여 여러 인접노드들 중에서 하나씩 탐색해가보는 방식이다.
함수 호출 한번이 각 한번의 노드 탐색이 되며 연이은 재귀 함수 호출은 더이상 탐색할 인접노드가 없을 경우 return을 통해서 backtracking으로 올라가게 된다.
사실 재귀함수를 호출하는 것 자체가 운영체제에서 제공하는 스택을 활용하는 것이다.

 

 

int visit[V];

void DFS(int curr) {
	visit[curr] = 1;
    
    for (int i = 0; i < adj[curr].size(); i++) {
    	int next = adj[curr][i];
        
        if (!visit[next]) {
        	DFS(next);
        }
    }
}

 

Stack을 이용한 구현과 비교하면 재귀 DFS 함수는 Stack에서 top 요소를 꺼내온 이후의 동작 Code를 그대로 옮겼다고 할 수 있다.
인접 노드를 Stack에 push하는 대신 인접 노드들을 DFS 함수로 재귀 호출하도록 하면 된다.
다른 그래프 탐색 방법이나 Stack을 이용할 때에도 마찬가지지만 중복 방문이 계속해서 허용된다면 탐색이 무한히 끝나지 않게 되므로 중복 처리가 중요하다.

 

 

int visit[V];

int DFS(int curr, int curr_cnt) {
    visit[start] = 1;
       
    for (int i = 0; i < adj[curr].size; i++) {
        int next = adj[curr][i];
        if (!visit[next])
        	return DFS(next, curr_cnt + 1);
    }
    
    return curr_cnt;
}

 

 

만약 경로 정보를 이용하고 싶다면 함수의 인자로서 활용할 정보를 넘겨주고 확인할 수 있다.
Stack을 이용한 구현에서 살펴봤던 예제와 마찬가지로 경로 상 몇개 이상의 노드가 필수라는 조건을 추가한다면 DFS 함수의 인자로 지나온 노드의 개수를 넘겨주도록 하면 된다.

 

 

---

 

 

DFS를 이용한 순열, 조합 구하기

 

DFS는 경로 정보를 이용할 수 있다는 점을 활용해 순열이나 조합을 구하는데 DFS를 이용할 수 있다.
이와 같이 직접적으로 그래프가 주어지는 문제가 아니어도 그래프로 문제를 풀어나가는 데에 자주 활용되는 것이 DFS이기 때문에 접근 방법을 기억해 두는 것이 좋다.

 

N개의 원소 중에서 M개를 선택하는 문제라면 다음 그림처럼 마치 트리와 같은 모습으로 표현할 수 있다.
트리의 각 단계(level)가 한번의 선택 기회가 되며 연결된 N개의 Node 중 하나씩 선택하며 M번 아래로 탐색해 내려가도록 진행하면 모든 경우의 수를 탐색시킬 수 있다.

 

 

3개의 원소 중 2개를 선택하는 경우의 수를 그래프로 표현한 모습

 

int arr[3] = {1, 2, 3};
int sel_arr[2];

void DFS(int sel) {
	if (sel == M) {
    	for (i = 0; i < N; i++) {
        	cout << sel_arr[i] << " ";
        }
        cout << "\n";
    } else {
    	for (i = 0; i < N; i++) {
        	sel_arr[sel] = arr[i];
            DFS(sel + 1);
        }
    }
}

 

 

중복 선택이 허용되지 않는 조합 문제라면 다음과 같은 모습의 트리로 나타낼 수 있다.
유사하게 DFS로 탐색해 내려가되 이미 앞서 선택했던 조합이 다시 탐색되지 않도록 방문 기록을 활용해주면 된다.

 

 

3개의 원소 중 2개를 중복되지 않게 선택하는 경우의 수를 그래프로 표현한 모습

 

int arr[3] = {1, 2, 3};
int sel_arr[2];

void DFS(int sel, int now) {
	if (sel == M) {
    	for (i = 0; i < N; i++) {
        	cout << sel_arr[i] << " ";
        }
        cout << "\n";
    } else {
    	for (i = now; i < N; i++) {
        	sel_arr[sel] = arr[i];
            DFS(sel + 1, i + 1);
        }
    }
}

DFS는 가장 기본이 되는 그래프 탐색 기법이기도 하지만 순열이나 조합을 찾는데에도 활용되는 만큼 반드시 익숙하게 다룰 수 있어야 한다.
특히 permutation이나 combination 등의 STL library를 사용하지 못하는 시험이나 환경이라면 이를 DFS로 직접 구현할 수 있는 능력이 필수라고 할 수 있다.