28장 그래프의 깊이 우선 탐색

28.1 도입

깊이 우선 탐색(depth-first search, DFS)은 그래프의 모든 정점을 탐색하는 방법 중 하나이다. 현재 정점과 인접한 간선들을 하나씩 검사하여, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 따라가기를 반복한다. 이 과정에서 더 이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 다음은 DFS를 구현한 코드이다.

// 그래프의 인접 리스트 표현
vector<vector<int>> adj;
// 각 정점을 방문했는지 여부를 나타냄
vector<bool> visited;

void dfs(int here)
{
	cout << "DFS visits " << here << endl;
    visited[here] = true;
    // 모든 인접 정점을 순회
    for(int i = 0; i < adj[here].size(); ++i) {
    	int there = adj[here][i];
        // 아직 방문한 적 없다면 방문
        if(!visited[there])
        	dfs(there);
    }
    // 더이상 방문할 정점이 없으니, 재귀 호출을 종료하고 이전 정점으로 돌아간다.
}
// 모든 정점을 방문한다.
void dfsAll() 
{
	// visited를 모두 false로 초기화
    visited = vector<bool>(adj.size(), false);
    // 모든 정점을 순회하면서, 아직 방문한 적 없으면 방문
    for(int i = 0; i < adj.size(); ++i)
    	if(!visited[i])
        	dfs(i);
}

여기서 유의할 점은 모든 정점에 대해 순서대로 dfs()를 호출하는 dfsAll() 함수의 존재이다. 그래프에서는 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에, dfs()만으로는 모든 정점을 순서대로 탐색하지 못한다.

 

# 깊이 우선 탐색의 시간 복잡도

인접 리스트를 사용하여 그래프를 표현한 경우 dfs()는 한 정점마다 한 번씩 호출되므로, 정확히 \(|V|\)번 호출된다. dfs() 한 번의 수행 시간은 모든 인접 간선을 검사하는 for문에 의해 지배되는데, 모든 정점에 대해 dfs()를 수행하고 나면 모든 간선을 한 번(방향 그래프의 경우) 또는 두 번(무향 그래프의 경우) 확인한다. 따라서 깊이 우선 탐색의 시간 복잡도는 \(O(|V|+|E|)\)가 된다.

인접 행렬을 사용하여 그래프를 표현한 경우 dfs()의 호출 횟수는 \(|V|\)번이다. 인접 행렬을 사용할 때는 dfs() 내부에서 다른 모든 정점을 순회하며 두 정점 사이에 간선이 있는가를 확인해야 하기 때문에 한 번의 실행에 \(O(|V|)\)의 시간이 든다. 따라서 전체 시간 복잡도는 \(O(|V|^2)\)이 된다.

 

# 예제: 두 정점이 서로 연결되어 있는가 확인하기

깊이 우선 탐색을 이용하면 그래프 상에서 두 정점 사이를 잇는 경로가 있는지 확인 할 수 있다. 어떤 정점 u에 대해 dfs(u)를 수행하면, u에서부터 간선들을 통해 갈 수 있는 모든 정점을 방문하게 된다. dfs(u)를 수행하고 visited[]를 참조하면 u로부터 각 정점에 갈 수 있는지를 쉽게 확인할 수 있다.

 

# 예제: 연결된 부분집합의 개수 세기

무향 그래프가 간선으로 서로 연결되지 않은 몇 개의 덩어리로 분리되어 있는 경우, 각 연결된 정점들의 부분집합을 컴포넌트(component) 혹은 요소라고 한다. 주어진 그래프가 몇 개의 컴포넌트로 구성되어 있는지는 모든 정점에 대해 dfs()를 수행하면 된다. 즉, dfsAll()에서 dfs()를 호출하는 횟수를 세면 그래프가 몇 개의 컴포넌트로 이루어져 있는지 확인할 수 있다.

 

# 예제: 위상 정렬

위상 정렬은 의존성이 있는 작업들이 주어질 때, 이들을 어떤 순서로 수행해야 하는지 계산한다. 예를 들어 다음은 김치찌개를 끓이기 위해서 해야하는 행동 목록이다.(순서 없이 나열했다)

1. 김치를 다진 마늘과 볶는다.
2. 볶은 김치에 돼지고기, 고춧가루, 다진 마늘을 넣고 더 볶는다.
3. 멸치 육수를 붓고 끓인다.
4. 파와 양파를 넣고 좀 더 끓인다.
5. 맛있게 먹는다.
6. 냉장고에서 재료들을 꺼낸다.
7. 김치를 썬다.
8. 돼지고기를 썬다.
9. 파와 양파를 썬다.
10. 멸치 육수를 낸다.

중요한 것은 이 작업들을 아무 순서로 수행할 수 없다는 점이다. 작업 1을 하려면 그 전에 작업 7을 완료해야 한다. 이렇게 어떤 작업 B를 하기 전에 반드시 작업 A를 해야 한다면, 작업 B는 작업 A에 의존한다고 하자. 각 작업을 정점으로 표현하고, 작업 간의 의존 관계를 간선으로 표현한 방향 그래프를 의존성 그래프(dependency graph)라고 한다. 의존성 그래프의 특성은 그래프에 사이클이 없다는 것이다. 따라서 이 그래프는 DAG가 된다. 의존성 그래프의 정점들을 일렬로 늘어놓고, 왼쪽에서부터 하나씩 수행한다고 하자. 이때 모든 의존성이 만족되려면, 모든 간선이 왼쪽에서 오른쪽으로 가야 한다. 그러니까 위에서 예시로 든 김치찌개를 끓이는 행동 목록을 의존성을 만족시키도록 왼쪽에서 오른쪽으로 정렬한다는 것이다. 이 DAG의 정점을 배열하는 문제를 위상 정렬이라고 한다.

위상 정렬을 구현하는 가장 직관적인 방법은 들어오는 간선이 하나도 없는 정점들을 하나씩 찾아서 정렬 결과의 뒤에 붙이고, 그래프에서 이 정점을 지우는 과정을 반복하는 것이다. 즉, dfsAll()을 수행하며 dfs()가 종료할 때마다 현재 정점의 번호를 기록한 후 dfsAll()이 종료한 뒤 기록된 순서를 뒤집으면 위상 정렬 결과를 얻을 수 있다. 따라서 dfs()가 늦게 종료한 정점일 수록 정렬 결과의 앞에 온다.

28.2 문제: 고대어 사전 - algospot.com :: DICTIONARY

# 그래프 모델링

// 고대어 사전 문제의 그래프 생성
// 알파벳의 각 글자에 대한 인접 행렬 표현
// 간선 (i, j)는 알파벳 i가 j보다 앞에 와야 함을 의미
vector<vector<int>> adj;

void makeGraph(const vector<string>& words)
{
	adj = vector<vector<int>>(26, vector<int>(26, 0));
	for (int j = 1; j < words.size(); ++j) {
		int i = j - 1;
		int len = min(words[i].size(), words[j].size());
		for (int k = 0; k < len; ++k) {
			if (words[i][k] != words[j][k]) {
				int a = words[i][k] - 'a';
				int b = words[j][k] - 'a';
				adj[a][b] = 1;
				break;
			}
		}
	}
}

 

# 인접한 단어들만 검사하기

makeGraph() 함수는 모든 단어 쌍을 검사하는 대신 사전상에서 인접한 단어들만을 검사한다. 즉, 사전에 세 단어 A, B, C가 순서대로 등장한다면, (A, C)는 검사하지 않고 (A, B)와 (B, C)만 검사한다. 그럼에도 모든 쌍을 검사했을 때와 마찬가지로 위상 정렬의 결과는 같다.

 

# 위상 정렬의 구현

// 깊이 우선 탐색을 이용한 위상 정렬

vector<int> seen, order;

void dfs(int here)
{
	seen[here] = 1;
	for (int there = 0; there < adj.size(); ++there)
		if (adj[here][there] && !seen[there])
			dfs(here);
	order.push_back(here);
}
// adj에 주어진 그래프를 위상정렬한 결과를 반환한다.
// 그래프가 DAG가 아니라면 빈 벡터를 반환한다.
vector<int> topologycalSort()
{
	int m = adj.size();
	seen = vector<int>(m, 0);
	order.clear();
	for (int i = 0; i < m; ++i)
		if (!seen[i])
			dfs(i);
	reverse(begin(order), end(order));
	// 만약 그래프가 DAG가 아니라면 정렬 결과에 역방향 간선이 있다.
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < m; ++j)
			if (adj[order[j]][order[i]])
				return vector<int>();
	// 없는 경우라면 깊이 우선 탐색에서 얻은 순서를 반환한다.
	return order;
}

28.4 오일러 서킷

오일러 서킷은 그래프의 모든 간선을 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 

정점의 차수(degree)는 한 정점에 인접한 간선의 수를 말한다. 차수가 짝수인 정점을 짝수점, 홀수인 점을 홀수점이라고 하자, 오일러 서킷은 모든 정점에 들어가는 횟수와 나오는 횟수가 같아야 하므로 그래프의 모든 정점들이 짝수점이어야만 오일러 서킷이 존재할 수 있다는 것을 알 수 있다. 마찬가지로 모든 정점이 짝수점이라면 오일러 서킷은 항상 존재한다.

# 오일러 서킷을 찾아내는 알고리즘 (깊이 우선 탐색)

// 깊이 우선 탐색을 이용한 오일러 서킷 찾기

vector<vector<int>> adj;

// 결과로 얻어지는 circuit을 뒤집으면 오일러 서킷이 된다.
void getEulerCircuit(int here, vector<int>& circuit)
{
	for(int there = 0; there < adj[here].size(); ++there){
		while (adj[here][there] > 0)
		{
			adj[here][there]--;
			adj[there][here]--;
			getEulerCircuit(there, circuit);
		}
	}
	circuit.push_back(here);
}