위상 정렬 (Topological Sort)

190616. 제 블로그 조회수의 상당수를 차지하는 글입니다. 특히 대학교 시험 기간인 6월에 많이들 찾아주시더라구요. 그런 것 치고는 글이 너무 오래 되어서, 글을 완전히 다시 쓰고 연습문제를 몇 개 추가했습니다.

 

위상정렬은 방향 그래프(directed graph) 문제에서 쓰입니다.
또는 직접 그래프가 주어지지 않는 경우에도, 문제에 나타난 요소들을 점으로 나타내고 그 사이에 화살표를 그렸을 때 방향 그래프가 나타나는데, 문제를 푸는 과정에서 위상 정렬이 꼭 필요한 경우도 있습니다.

먼저 위상 정렬을 대강의 느낌으로 설명해 보려고 합니다.
a → b를 "a가 충족되어야만 b를 할 수 있다"는 뜻으로 생각해봅니다.
예를들어 a가 세탁기를 돌리기, b가 건조기 사용하기라면, 세탁기를 돌리는 일을 마쳐야 건조기를 시작할 수가 있습니다.
건조를 끝낸 후에 세탁기를 돌릴 수는 없겠죠.
또한 세탁기 작동이 끝난 직후 바로 건조를 시작해야 하는 건 아닙니다. 그 사이에 잠깐 물을 마셔도 되고, 심지어는 세탁물을 그대로 두고 청소를 하고 쌀도 씻고 맨손운동 좀 하고 장을 봐오고 나서야 건조기를 시작해도 논리적으로는 문제가 없습니다. 아무튼 순서는 맞으니까요.

이제 a → b의 조건을 그래프로 한 번 그려봅시다.

해야 할 일의 목록을 만들고 이들 간의 선후관계를 그렸습니다.
이제 무엇부터 해야 할까요? 동시에 두 일을 하지는 않고, 하나씩 완전히 마친 후 다른 일을 한다고 가정합니다.

예를 들면 7, 5, 3, 11, 8, 2, 9, 10의 방법이 있어 보입니다.
이 순서대로 점들을 따라가면 확실히 순서가 예쁘게 정리되는 것 같습니다.
7, 5, 3, 2, 8, 11, 9, 10은 2가 11보다 (떨어져 있지만) 먼저 왔으므로 순서에 어긋납니다.

이런 예쁜 순서를 하나 찾는 과정이 위상 정렬(topological sort)입니다.
'정렬'이라는 이름이 붙은 이유는 모든 점이 한 번씩 나타나야 하고 결국 조건에 맞게 재배열하는 과정이기 때문입니다.
또 결과 자체를 위상 정렬이라고 부르기도 합니다. 그러니 "이 그래프에서 위상 정렬을 하겠다"라고도 말할 수 있고, "이 그래프에 대해 7, 5, 3, 11, 8, 2, 9, 10은 옳은 위상 정렬이다"라고도 말할 수 있습니다.

 

---

 

조그마한 그래프라면 손으로 위상 정렬을 구할 수 있을 것 같습니다.
그런데 위상 정렬을 알고리즘으로 할 수는 없을까요?
그보다 위상 정렬이 모든 그래프에 대해 존재하기는 할까요?
1 →  2 → 3 → 1 의 그래프를 봅시다. 세 개의 일이 꼬리에 꼬리를 물고 있어서 어느 것도 먼저 시작할 수가 없지요.
이렇듯 모든 그래프에 위상 정렬이 존재하는 것은 아닙니다.

먼저 그 조건에 대해 고민해 보겠습니다.
이 그래프에는 사이클(자기 자신으로 돌아오는 경로)이 없어야 한다는 중요한 조건이 있습니다.
사이클이 있다면 위상 정렬이 불가능하다는 걸 증명할 수 있습니다.
여기서 잠깐, 사이클이 없는 방향 그래프를 영어로 하면 directed acyclic graph, 줄여서 DAG라고 부릅니다.
DAG는 PS를 하는 사람들 사이에서 자주 쓰이는 단어이므로 알아두면 좋습니다.

이 필요조건이 실은 필요충분조건입니다.
즉, 사이클이 존재하면 위상 정렬이 무조건 불가능하지만,
반대로 사이클이 없다면 항상 위상 정렬이 가능합니다. 그러니 DAG는 항상 위상 정렬이 가능합니다.

이제 위상 정렬을 찾는 알고리즘에 대해 생각해봅니다.
이 글에서는 두 가지를 설명합니다.

 

첫 번째 방법

이 방법은 점을 하나씩 선택해 나가면서, 위상정렬을 앞에서부터 만들어 나갑니다.
위에서 말한 조건이 필요충분조건임을 이 방법으로 구성적 증명(constructive proof)을 할 수 있습니다.

각각의 점에서 "나를 향해 화살표를 쏘고 있지만, 아직 선택되지 않은 점의 수"에 대해 생각해 보세요.
이 개수는 최소 몇 개인가요? 0개입니다. 많으면 많아질 수도 있겠죠.

위상정렬을 앞에서부터 만들어 나가면서 몇 개의 점을 선택했을 때,
다음으로 올 수 있는 점은 이 값이 0인 점 뿐임을 아시겠나요?
0이 아니라면, 나를 향해 화살표를 쏘고 있으면서 아직 선택되지 않은 점이 있다는 것이고,
그 점을 선택하지 않은 채 벌써 나를 선택해 버린다면(나중에 해야 할 일을 먼저 한다면),
그 점을 언젠가 선택해야 하긴 하니 지금보다 나중에 선택할 텐데, 그러면 순서가 어긋나 버릴 테니까요.

이 값이 0인 점이 한 개거나, 여러 개 있을 수 있습니다.
그중 아무거나 선택해서 지금까지 만들어진 위상 정렬에 추가해봅니다.
그러면 이 점에서 화살표를 쏘고 있는 모든 점들에 대해 "나를 향해 화살표를 쏘는, 선택되지 않은 점의 수"는
동시에 1씩 줄어들겠죠.
줄어들어서 0이 된 점이 있다면 또 그 다음 선택 가능한 후보가 되겠습니다.

pseudo-code는 아래와 같습니다.

1       algorithm toposort_1() is:
2           indegree ← {i번째 정점에 대해, i번째 정점을 향하는 간선의 개수};
3           result ← (빈 배열)
4           while indegree[x] == 0이고 아직 선택하지 않은 x가 있는 동안:
5               indegree[x] == 0이고 아직 선택하지 않은 x를 하나 잡는다;
6               result의 제일 뒤에 x를 추가한다;
7               for x→y가 존재하는 모든 y에 대해:
8                   indegree[y] ← indegree[y] - 1
9           return result

 

두 번째 방법

DFS를 아셔야 하는 방법입니다.
신기하게도 위상 정렬을 뒤에서부터 만들어 나가는 알고리즘입니다.

방문하지 않은 모든 점들에 대해 DFS를 수행합니다.
DFS가 호출되면 일단 방문했다는 처리를 한 후, 나에게서 출발하는 모든 화살표의 끝점에 대해 방문을 안 했다면 DFS를 수행합니다.
그리고 DFS에서 탈출할 때(=반환할 때 =호출 stack에서 pop할때) 현재 점을 지금까지의 위상 정렬 결과의 제일 앞에 추가합니다.
예를 들어 지금까지 [10, 2, 5]를 만들었는데, 3에서 return 한다면 [3, 10, 2, 5]가 되게 하는 방법입니다.

보통은 배열의 가장 앞에 추가하는 연산보다 뒤에 추가하는 연산이 쉽기 때문에,
일단 뒤에 추가한 뒤 결과를 뒤집는 식으로 구현합니다.
즉 [5, 2, 10]을 [5, 2, 10, 3]으로 만들며 모두 순회한 뒤 결과를 통째로 뒤집습니다.

pseudo-code는 다음과 같습니다.

1       algorithm dfs(x) is:
2           visit[x] = True;
3           for x->y가 있는 모든 y에 대해:
4               if not visit[y]:
5                   dfs(y);
6           x를 history의 제일 뒤에 추가
7       
8       algorithm toposort_2() is:
9           visit ← (False for all vertex);
10          history ← (빈 배열);
11          for visit[p] == False인 모든 p에 대해:
12              dfs(p);
13          result ← (history의 순서를 뒤집은 배열)
14          return result

"방문한 적이 없는 모든 p에 대해: dfs(p);"를 보고, 왜 말을 돌려서 하지? 하고 생각할 수도 있습니다.
처음 시작할 때는 아무 것도 방문하지 않은 상태니까, 그냥 모든 점에 대해 한 번씩 dfs()를 하면 되는 거 아냐?라고요.
그런데 한 점에 대한 dfs()에서 다른 점을 방문할 수 있기 때문에 모두 확인해줘야 합니다.
예를 들어 3개의 점으로 이루어진 그래프가 있다면, dfs(1); dfs(2); dfs(3);을 해주면 되지 않느냐고 하지만,
dfs(1)에서 dfs(2)나 dfs(3)을 호출한다면 더 이상은 그 점을 탐색하면 안 되겠죠.

첫 번째 방법에 비해 "당연히 순서가 올바른 위상정렬이 될 것이다"라는 느낌이 확 안 듭니다. 비직관적이라고도 하지요.

 

---

 

연습 문제

개념 문제

알고리즘 등의 과목으로 시험 공부를 하시는 분들은 이런 문제가 필요하시겠다 싶어서 만들었습니다.

Q1. 사이클이 있는 방향 그래프에 위상 정렬이 존재하지 않음을 증명하시오.
Q2. 사이클이 없는 방향 그래프(DAG)에 위상 정렬이 존재함을 증명하시오.
Q3. 위상 정렬 방법은 모든 그래프에 대해 유일한가?

Q4-1. 유일하지 않다면, 위상 정렬 방법이 유일한 그래프가 있는가? 있다면 예시를 들어라.
Q4-2. 위상 정렬 방법이 3가지인 그래프가 있는가? 있다면 예시를 들어라.
Q4-3. 위상 정렬 방법이 2¹⁰=1024가지인 그래프가 있는가? 있다면 예시를 들어라.

아래 문제는 그래프가 DAG임을 가정합니다.

Q5-1. toposort_1()의 4-8번 줄의 반복문이 끝난 후 result 배열의 크기는 항상 정점의 개수와 같은가? 증명하시오.
Q5-2. toposort_1()의 8번 줄에서, indegree의 값이 음수가 되는 일은 일어나지 않는가? 이유를 들어 설명하라.
Q5-3. 같은 줄에서 y에 대해 말할 수 있는 것(e.g. 항상 이전에 선택된 정점이다, 항상 아직 선택되지 않은 정점이다 등)이 있는가?

Q6. toposort_2()의 11-12번 줄의 반복이 끝나고 나서, history 배열의 크기가 항상 정점의 개수와 같은가? 증명하시오.
Q7. toposort_2() 알고리즘이 옳게 작동함을 보이시오. 즉 결과가 올바른 위상정렬임을 보이시오.

Q8. 방향 그래프가 주어지면 사이클이 존재하는지를 판단하는 알고리즘을 제안하시오.

정답에 대한 힌트는 바로 아래에 접어서 두겠습니다.

1. 사이클이 있다면 사이클 위의 서로 다른 두 정점을 아무거나 잡아 a, b라고 합니다. 이제 증명해 보세요.

2. 갑자기 난이도가 너무 높아졌나요? 맞습니다. 시험이라면 저는 toposort_1() 알고리즘이 끝까지 작동하므로, 를 길게 풀어서 쓰면 될 거라고 생각합니다. 대신 모든 지점을 엄밀하게 증명해야겠죠. 아래 문제의 내용도 일부 포함하게 되겠네요.

4-2. 여기서 1→(2,3,4)→5 형태의 그래프는 가운데 세 개를 배열하는 방법이 3!=6가지이므로 오답입니다. 정답은 있습니다.
4-3. 마찬가지로 있습니다. 이지선다를 열 번 하도록 강제하는 방법이 뭘까요?

5-1. 정점을 하나 선택할 때마다 result의 크기도 늘어날 테니, 선택하는 횟수가 정점 개수만큼이 됨을 보입시다.
5-3. 항상 아직 선택되지 않은 정점입니다. 그것 말고 말할 수 있는 점은 없어 보여요.

6. 위의 5-1과 마찬가지로, visit 횟수가 몇 번인지를 생각해봅니다.
7. a→b의 화살표에 대해, result 위에서 항상 a가 b보다 앞에 있음을 보이면 됩니다. 그래도 막막하다면, a와 b 중 먼저 dfs가 호출되는 쪽이 어느 쪽인지는 두 가지 경우가 있죠? 각각을 따져봅니다.

8. 이제 쉽죠?

 

실전 문제

실제 코딩을 연습할 문제입니다.

그 전에 잠깐 짚고 넘어가겠습니다.
위의 pseudo-code에 대한 C++ 구현을 보여드리고 넘어가는 게 좋을 것 같습니다.

int indegree[maxN];
vector edge[maxN]; // adjacency list입니다.
int N;
int result[maxN];
void toposort1() {
    for(int i = 1; i <= N; ++i) for(int j : edge[i]) ++indegree[j];
    queue Q;
    for(int i = 1; i <= N; ++i) if(indegree[i] == 0) {
        Q.push(i);
    }
    int resN = 0;
    while(!Q.empty()) {
        int x = Q.front(); Q.pop();
        result[++resN] = x;
        for(int y : edge[x]) {
            --indegree[y];
            if(indegree[y] == 0) Q.push(y);
        }
    }
}

 

bool vis[maxN];
vector edge[maxN]; // adjacency list입니다.
int N;
int result[maxN], resN;
void dfs(int x) {
    vis[x] = 1;
    for(int y : edge[x]) if(!vis[y]) dfs(y);
    result[++resN] = x;
}
void toposort_2() {
    resN = 0;
    for(int i = 1; i <= N; ++i) vis[i] = 0;
    for(int i = 1; i <= N; ++i) if(!vis[i]) dfs(i);
    for(int l = 1, r = N; l < r; ++l, --r) {
        swap(result[l], result[r]);
    }
}

위의 개념 문제에서 증명한 성질을 많이 사용했습니다. 전체적으로 코드를 간결하게 했습니다.
예를 들어, toposort_1()에서는 지금 queue에서 뽑은 점을 이미 선택했는지의 여부를 전혀 확인하지 않지요. 또 toposort_2()에서는 vis 체크가 되지 않은 점을 i가 증가하는 순서대로 한 번만 보면 모두 확인할 수 있음을 당당하게 사용합니다. 이래도 될까요? 네, 됩니다.

 

처음이시라면 BOJ 2252 줄 세우기(링크)를 비롯해 BOJ의 위상 정렬 태그(링크)가 붙은 문제가 좋을 것 같습니다.

또 좋은 문제를 찾으면 여기에 추가하겠습니다.