January 12, 2021 13 min to read

그래프 자료구조 ②:깊이 우선 탐색①

DFS, 위상정렬, 오일러 서킷에 대해서 알아봅시다!

개요

사실 블로그에 글을 적는것은 순전히 저만을 위해서 적는 것이었습니다. 그래서 스택, 큐, 리스트, 트리 너무 간단해서 머리속에 내장되있다고 생각했던것들은 일부로 적지 않고 필요한 것만 적고 있었는데, 최근 BFS를 이용하면 뚝딱 하고 풀리는 쉬운 문제(백준 16953 A → B)의 답을 쉽게 생각해내지 못한것을 반성하는 겸 하여, BFS와 DFS, 그리고 이와 밀접한 관련이 있는 몇몇 알고리즘들을 이 글에서 소개해 보고자 합니다.

그래프의 순회는, 트리의 순회와 달리 탐색 과정에서 어떠한 간선이 사용되었는지, 또, 어떤 순서로 탐색되었는지를 통해서 그래프의 구조를 유추할 수 있기에, 중요하게 다루어야 하는 부분이기도 하다는 점을 다시 한번 상기하면서, 이 글을 쭉 적어나가보겠습니다.

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].sizse();++i){
    	int there = adj[here][i];
        if(!visited[here])
        	dfs(there);
    }
}

void dfsAll(){
    visited = vector<bool>(adj.size(), false);
    for(int i = 0; i < adj.size(); ++i){
    	if(!visited[i])
        	dfs(i);
}

위상정렬

DFS를 유용하게 써먹는 알고리즘 중 하나가 위상정렬 입니다. 거창한 이름과는 다르게, 일상생활에서도 이 알고리즘을 적용할 수 있는 상황이 많습니다.

위상정렬은 의존성이 있는 작업들이 주어질 떄, 이들을 어떤 순서로 수행해야 하는지를 계산하는 알고리즘 입니다. 예를 들어서, 김치찌개를 끓이기 위해서는 아래와 같은 일들을 해야합니다.

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

이 과정에서 주목해야 할 것은, 이 작업들을 배치하기 위해서는 아무렇게나 배치할 수 없다는 것입니다. 멸치 육수를 붓기 위해서는, 멸치 육수를 내야하고, 멸치 육수를 내기 위해서는, 냉장고에서 재료들을 꺼내야 하는 등, 순서가 정해져 있기 때문이죠. 이렇게 작업 B를 하기 전에 반드시 작업 A를 해야 한다면, 작업 B가 작업 A에 의존한다고 합니다.

각 작업을 정점으로 표현하고, 작업 간의 의존 관계를 간선으로 표현한 방향 그래프를 의존성 그래프(dependancy graph)라고 합니다. 작업 v가 u에 의존한다면, 그래프는 (u,v) 간선을 포함하게 됩니다. 의존성 그래프에서 가장 중요한 특징은, 그래프에 사이클이 없다는 점 이고, 즉 사이클 없는 방향 그래프, DAG 입니다. (간단히 생각해 봅시다. A를 하기 위해서는 B를 해야하고, B를 하기 위해서는 C를 해야하는데, C를 하기 위해서는 A를 해야 한다고 합시다. A,B,C 작업중 어느것도 할 수 없겠죠?)

의존성 그래프의 정점을 일렬로 늘어놓고, 왼쪽부터 하나씩 차례로 수행한다고 합시다. 이때, 수행되는 순서가 의존성이 만족되도록 정렬하는 알고리즘이 위상정렬 입니다.

위상정렬을 구현하는 가장 직관적인 방법은 들어오는 간선이 하나도 없는 정점을 찾아서, 정렬 결과의 뒤에 붙이고, 그래프에서 그 정점을 지우는 과정을 반복하는 것입니다만, 깊이 우선 탐색을 사용하면, 더 간단하게 이 문제를 해결할 수 있습니다.

그 비결은 모든 정점에 대해서 DFS를 수행하며(코드 1의 dfsAll()이용), DFS가 종료할 때마다 현재의 정점을 기록하는 것입니다. 그리고 모든 정점에 대해서 DFS를 다 수행했다면, 그 결과를 뒤집으면 위상정렬 결과가 나옵니다. 따라서, DFS가 늦게 종료한 정점일수록 정렬 결과의 앞에 오게 됩니다.

자세한 정당성 증명은 다음 포스팅에서 설명하겠지만, 간단한 귀류법으로도 위상정렬의 정당성을 보일 수 있습니다.

이 방법으로 정렬한 간선을 일렬로 나열했을 때, 오른쪽에 있는 정점 \(u\) 에서 왼쪽에 있는 정점 \(v\)로 가는 간선, 즉 정렬 결과를 역행하는 간선이 있다고 합시다. (== 정렬 결과의 정당성을 깨트림) 정렬 결과로부터 알 수 있는 사실은, dfs(u)가 종료한 후에 dfs(v)가 종료했다는 것입니다. 그런데, dfs(u)는 종료하기 전에 모든 인접한 간선을 보기 때문에, dfs(u)는 종료하기 전에 간선 \((u,v)\)또한 검사했을 것입니다. \(v\)의 방문여부를 나타내는 visited[v]가 true인 상황과 false인 상황 두가지를 모두 생각해 봅시다.

1. visited[v]가 false인 상황 : dfs(u)는 dfs(v)를 호출했을 것입니다. 그리고 dfs(v)가 종료한 후에야 dfs(u)가 종료 되었겠지요. 따라서 이 경우는 \(v\)가 \(u\)의 왼쪽에 있을 수 없습니다.

2. visited[v]가 true인 상황 : \(v\)를 방문했다면, dfs(v)가 이미 한번 호출되었어야 합니다. 그런데 dfs(v)가 dfs(u)보다 먼저 끝났다는 말은, dfs(v)가 호출 스택에 있는 상황에서(즉 안끝난 상황에서), dfs(u)가 실행되었다는 말인데, 그렇게 되려면 \(v\)에서 \(u\)로 가는 경로가 있어야 하고, 여기에 \((u,v)\)를 붙이면 사이클이 되버립니다. 이는 원래 그래프가 DAG라는 가정에 모순이기에 이 경우도 있을 수 없습니다.

두 경우 모두 우리의 가정에 모순이므로, 오른쪽에서 왼쪽으로 가는 간선 \((u,v)\)는 존재하지 않고, 이 결과는 적절한 위상정렬 결과임을 알 수 있습니다.

아래는 DFS를 이용한 위상정렬 코드입니다.

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(there);
    order.push_back(here);
}
//adj에 주어진 그래프를 위상정렬한 결과를 반환
//그래프가 DAG가 아니라면 빈 벡터를 반환
vector<int> topologicalSort() {
    int m = adj.size();
    seen = vector<int>(m,0);
    order.clear();
    for(int i = 0; i < m; ++i) if(!seen[i]) dfs(i);
    reverse(order.begin(),order.end());
    //만약 그래프가 DAG가 아니라면 정렬 결과에 역방향 간선이 있을것
    for(int i = 0; i < m; ++i)
        for(int j = i + 1; j < m; ++j)
            if(adj[order[j]][order[i]]) return vector<int>();

    return order;
}

문제를 풀 때, 특정한 순서에 관한 언급이 있고, 그 순서에 따라서 정렬을 해야하는 상황이 있다면, 위상정렬을 떠올리면 많은 도움이 될 것입니다.

오일러 서킷, 오일러 트레일 찾기

오일러 서킷의 정의

DFS를 이용하는 또 다른 문제로, 그래프의 모든 간선을 정확히 한 번씩 지나서, 시작점으로 돌아오는 경로를 찾는 문제가 있습니다. 이와 같은 경로를 그래프 이론에서는 오일러 서킷(Eulerian curcuit)라고 하며, 종이에서 펜을 떼지 않고 주어진 도형의 모든 선을 정확히 한번씩 그리고 시작점으로 돌아오는 한붓 그리기 문제로 우리에게 친숙한 문제이기도 합니다. 방향이 존재하는 유향 그래프, 방향이 없는 무향 그래프 두 그래프에 대해서 모두 풀 수 있지만, 우선 간단한 무형 그래프에 대해서부터 다루기로 하겠습니다.

오일러 서킷이 언제 존재할 수 있는지 생각하기 위해서는, 반대로 언제 존재할 수 없는지를 생각해 보면 좋습니다. 당연한 사실 하나는, 그래프의 간선들이 두개 이상의 컴포넌트로 나눠져 있을떄 입니다. 정점이 아니라는 사실에 유의합시다. 상당히 간과하기 쉬운 부분인데, 간단한 예시를 하나 들어보겠습니다. 정점 A,B,C가 있고, 간선이 (A,B), (B,A) 만 존재하는 방향 그래프라고 합시다. 이때, 정점은 두개의 컴포넌트로 쪼개져 있지만, 오일러 서킷은 존재하지요.

오일러 서킷을 찾는 알고리즘 - 착안 아이디어

우선 최대한 많은 간선을 지나는 경로를 그리는 알고리즘이 있고, 우리가 그것을 사용할 수 있다고 합시다. 이 경로의 시작점을 \(u\), 끝점을 \(v\)라고 합시다. 오일러 서킷이 존재한다면, 이 방법이 오일러 서킷을 찾아 주겠지만, 그런 경로가 존재하지 않는다면, 모든 간선을 지나지 못하고 끝나게 되겠죠. 이 경로에서 \(v\)에 인접한 모든 간선은 이미 지난 후 라는것을 우리는 알 수 있습니다. 만약 그렇지 않다면, 그 간선을 따라서 경로를 연장할 수 있고, 기존에 찾은 결과물은 최선이 아니니까요. 이 외에도 \(u\)와 \(v\)에 대해서 몇가지를 더 알 수 있습니다.

1. \(u\ne v\)인 경우는, 항상 \(v\)는 홀수개의 간선과 인접해 있을 겁니다. \(v\)를 지나가기 위해서는 들어가는데 하나, 나가는데 하나의 간선이 필요하고, 때문에 \(v\)로 들어가서 더이상 나올 수없다는 말은 인접한 간선의 수가 홀수라는 의미이기 때문입니다.
2. \(u=v\)인 경우는, 항상 \(v\)는 짝수개의 간선과 인접해 있을 겁니다. \(u\)에서 나가는 것으로 시작해서 다시 \(u\)로 돌아와서 나갈 수 없다면, 그것은 인접한 간선의 수가 짝수라는 의미이기 때문입니다.

여기에서 우리는 각 정점에 인접한 간선의 수, 즉 정점의 차수(degree)가 오일러 서킷에 상당히 중요한 부분을 차지할 것이라는 예측을 할 수 있습니다. 차수가 홀수, 짝수인 점을 각각 홀수점, 짝수점 이라고 합시다. 앞에서 알아본 \(u\)와 \(v\)의 정보에서 알 수 있듯, 오일러 서킷이 존재하려면, 모든 정점이 짝수점이어야 합니다. (오일러 서킷은 \(u=v\)인 경우니까요)

홀수점이 하나라도 있을 때 오일러 서킷이 존재하지 않는다는 사실은 알았습니다. 그 역, 즉 “홀수점이 없을때 오일러 서킷이 존재한다” 는 성립할까요? 결론부터 말하자면 예 입니다. 제가 본 “프로그래밍 대회에서 배우는 알고리즘 문제해결 전략”이라는 책에는 ‘항상 오일러 서킷을 만들어 낼 수 있다’라는 한마디 만으로 끝내, 개인적으로 좀 아쉬워서 간략하게나마 이 포스팅에서 증명을 하고 넘어가려고 합니다… 라고 쓸려고 했는데, 결국 증명이 아래에서 소개할 알고리즘의 당위성을 설명하는 내용이다 보니, 오일러 서킷을 찾아내는 알고리즘을 소개하도록 하겠습니다.

오일러 서킷을 찾는 알고리즘 - 본격적 설명

어떤 그래프의 모든 정점이 짝수점이고, 모든 간선이 하나의 컴포넌트에 폼함 되어 있다고 합시다. 이때 임의의 정점 \(u\)에서 시작해, 아직 따라가지 않은 간선 하나를 따라가며 임의의 경로를 만드는 함수 findRandomCircuit(u)를 만들어 봅시다. 이 함수는 현재 인접한 정점 중 쓰이지 않은 간선 중 하나를 임의로 따라가며, 더이상 따라갈 간선이 없을때 종료합니다.

이 함수가 찾는 경로의 끝점은 무조건 시작점 입니다. 모든 정점이 짝수점이기 때문에, 한 정점에 대해서 출입 횟수가 같을수 밖에 없기 때문이라는 사실을 간단히 알 수 있지요. 하지만, 이 함수가 오일러 서킷을 무조건 찾는것은 아닙니다. 아래의 그림은 findRandomCircuit()이 생성할 수 있는 경로지만, 오일러 서킷이 아닌 서킷을 찾은 경우입니다.

이 경우에는 방문했던 정점들을 다시 돌아보면서, 아직 방문하지 않은 간선이 있는 정점을 찾습니다. 그래프의 모든 간선이 하나의 컴포넌트에 있기 때문에, 오일러 경로를 찾지 못했는데, 방문하지 않은 간선이 없는 경우는 존재하지 않습니다. 해당하는 정점을 찾고, 그 정점을 \(v\)라고 합시다.

\(v\)에서 아직 사용하지 않은 간선의 개수 역시 짝수개 입니다. 원래 짝수개의 정점이 있었고, 한번이상 들어오고 나가고 하는 과정을 거치면서 짝수개수의 간선을 사용했기 때문이죠. 따라서 \(v\)에서 시작하도록 findRandomCircuit()을 실행하면, 새로운 하나의 서킷을 얻을 수 있습니다.

그런데 우리가 원하는 것은 분리되어 있는 여러 서킷들의 집합이 아닌, 하나의 모든 간선을 지나는 서킷 입니다. 다행히, 여러 서킷들의 집합을 합치는 것은 가능한 일이며, 그렇게 어려운 작업이 아닙니다. 처음에 찾은 서킷을 \(v\)에서 자른 뒤, 새롭게 찾은 서킷을 끼워넣으면 쉽게 더 큰 서킷을 얻을 수 있기 때문이지요.

이와 같은 일을 서킷이 모든 간선을 포함할 때 까지 반복하면, 오일러 서킷을 쉽게 찾을 수 있습니다.

오일러 서킷을 찾는 알고리즘 - 간단한 증명

어떤 그래프 \(G\)의 모든 간선이 하나의 컴포넌트로 연결되어 있고, 모든 정점이 짝수점이라고 합시다. \(a_1\)에서 탐색을 시작해 봅시다. \(a_1\)은 짝수점 이고, 모든 간선이 하나의 컴포넌트로 이루어져 있으므로, 간선으로 연결된 다른 정점이나, 루프가 있다면 자기 자신에게 간선을 하나 사용해서 갈 수 있습니다. 이렇게 해서 도착한 간선을 \(a_2\)라고 하고, \(a_2\)에 대해서도 위와 똑같은 이유로, 똑같은 과정을 실시해서, 임의의 서킷 \(C\)를 하나 찾습니다. 만약 \(C\)가 모든 간선을 포함한다면, 증명 완료입니다. 그렇지 않다면, 그래프 \(G\)에서, 서킷 \(C\)를 빼서, 부분 그래프 \(H\)를 만듭시다. 그래프 \(H\)에서도 모든 정점은 짝수점이며, 임의의 서킷 \(C_1\),\(C_2\)…을 찾을 수 있습니다. 이때, \(H\)에서 만들어진 서킷들이 지나는 정점중 적어도 하나는 \(C\)에 속해 있습니다. 따라서 이를 모두 연결하면, 큰 서킷을 만들 수 있고, 이 방법으로 오일러 서킷을 찾을 수 있습니다.

오일러 서킷을 찾는 알고리즘 - DFS를 이용한 구현

웨에서 설명한 방법을 곧이 곧대로구현하기는 사실 꽤나 까다로운 일입니다. 두 서킷을 합치는데에는 두 서킷의 길이에 비례하는 시간이 걸리기 때문이죠. 하지만, DFS를 이용한 구현을 이용하면 이러한 불편 없이 간단하게 오일러 서킷을 찾는 알고리즘을 설계할 수 있습니다.

이 알고리즘을 구현하는 핵심 아이디어는, findRandomCurcuit()을 DFS 처럼 재귀호출로 구현하는 것입니다. findRandomCurcuit(u)는 \(u\)와 인접한 간선을 검색하면서, 아직 사용하지 않은 간선 \((u,v)\)가 있다면, findRandomCurcuit(v)를 호출하는 것이지요. 그리고 더이상 따라갈 간선이 없으면 재귀 호출을 종료하고 리턴 합니다. 이때 이때까지 호출한 정점들을 모으면, 그것이 하나의 서킷이 됩니다. 임의의 서킷을 찾았으므로, 그게 오일러 서킷인지 확인하기 위해서, 이때까지 거친 정점들을 순회하면서, 남아있는 간선이 있지 확인해야 하는 과정또한 있습니다. 이는 재귀호출의 성질을 이용해서 깔끔하게 해낼 수 있는데, 재귀호출의 리턴 순서는, 호출한 순서의 반대이므로, 그 과정에서 이때까지 호출한 정점의 간선들을 확인해 보고, 만약 남아있는 간선이 있다면, 그 정점에 대해서 다시 함수를 호출하여, 원래의 간선에 끼워 넣으면 됩니다.

아래는 위의 아이디어를 코드로 옮긴 것입니다. 여기서 주목해서 보아야 할 부분은, 위에서 설명한 남은 간선이 있을 때, 새로운 서킷을 만들어서 기존 서킷에 끼워넣는 부분이 없다는 것인데, 비결은 각 간선을 따라갈 때, 경로에 추가하는 것이 아닌, 호출이 끝나고 반환될 때, 추가하는 것입니다. 결과적으로는 경로의 끝점부터 역순으로 정점들이 추가되는 것이지요. 이 방법의 단점이라면, 결과로 얻은 간선을 reverse등으로 뒤집어 줘야 한다는 것이지만, 구현이 간단해 지기 때문에 유용한 테크닉 입니다.

vector<vector<int> > adj;//그래프의 인접 행렬 표현 adj[i][j] : i와 j사이의 간선 수
//무향 그래프에서 오일러 서킷 탐색
void getEulerCurcuit(int here, vector<int> &curcuit){
    for(int there = 0; there < adj[here].size(); ++there){
        while(adj[here][there] > 0){
            adj[here][there]--;
            adj[there][here]--;//유향 그래프일 경우 이것을 지우면 된다
            getEulerCurcuit(there,curcuit);
        }
    curcuit.push_back(here);
}

위 코드의 시간복잡도를 생각해 보면, 각 간선을 따라갈 때마다 getEulerCurcuit()을 호출하고, 그 내부에서는 \(O(\|V\|)\)만큼의 반복문을 돌리므로, 시간 복잡도는 \(O(\|V\|\|E\|)\)가 됩니다. 인접 리스트 구현으로 한다면 \(O(\|E\|)\)만에 할 수 있지만, 이러면 반대쪽에서 오는 간선을 지우는 구현이 조금 더 까다로워 지겠죠(유향 그래프일 경우에는 이 연산을 안하니까 상관 없겠지만요…)

오일러 트레일을 찾기

오일러 트레일은 모든 간선을 정확히 한번씩 지나지만, 시작점과 끝이 다른 경로를 의미합니다. 사실 오일러 서킷을 찾는 알고리즘을 약간만 변형하면 오일러 트레일을 찾는 문제를 풀 수 있습니다.

정점 \(a\)에서 시작해서 \(b\)로 끝나는 오일러 트레일을 찾고 싶다고 합시다. \(a\)와 \(b\) 사이에 새로운 간선 \((b,a)\)를 추가한 다음 오일러 서킷을 찾은 다음, \((b,a)\)를 끊어내면 됩니다.

마무리

이번 포스팅에서는 그래프의 탐색 방법 중 하나인 깊이 우선 탐색과, 간단한 깊이 우선 탐색의 응용에 관해서 정리해 보았습니다. 다음 글에서는 조금 더 심화된 내용인, 그래프의 간선 분류를 알아볼 것이고, 그래프의 간선 분류와 DFS를 함께 응용하여 할 수 있는 여러 흥미로운 내용들에 대해서 다뤄볼까 합니다.

읽어주셔서 감사합니다.

참고한 글

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(구종만 저)
http://mip.hannam.ac.kr/courses/network/chap4/chap4.html