[실전 알고리즘] 0x11강 - 위상 정렬_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x1A강 - 위상 정렬에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

안녕하세요, 이번 시간에는 위상 정렬을 다뤄보도록 하겠습니다.

 

위상 정렬은 방향이 있는 그래프에서 정점들을 정렬하는 방법입니다. 본격적인 정의를 배워보기 전에 실생활의 쉬운 예시를 들어 설명을 해보겠습니다.

 

대학교에서 선수 과목이 있는 과목들이 있습니다. 예를 들어 프로그래밍1 과목을 들어야 프로그래밍2 과목을 들을 수 있게 해놓은 것과 같은 상황을 말합니다.

 

이러한 관계들을 고려한 전체적인 과목 배치가 위와 같다고 해봅시다. 이 과목 배치 상에서 모든 과목을 수강하고 싶다고 하면 어떤 순서로 과목을 들어야할까요?

 

다양한 방법이 존재할 것입니다. 이산수학, 프로그래밍1, 프로그래밍2, 자료구조, 알고리즘, 객체지향 프로그래밍 순으로 들어도 되고, 이산수학을 최대한 미루고 미뤄 프로그래밍1, 프로그래밍2, 객체지향 프로그래밍, 자료구조, 이산수학, 알고리즘 순으로 들을 수도 있을 것입니다.

 

그러나 선수 과목을 지켜야하기 때문에 알고리즘을 먼저 듣고 이산수학을 그 다음에 듣는 것은 불가능할 것입니다.

 

이 때 과목을 정점으로 나타내고 과목의 선후 관계를 간선으로 나타낸 상황을 생각해봅시다.

 

그러면 이와 같은 모양이 나오게 됩니다. 이제 위상 정렬에 대해 이해할 수 있습니다. 위상 정렬은 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬입니다. 예를 들어 주어진 그래프를 보면 A에서 C로 가는 간선이 있으니 위상 정렬을 했을 때 A는 C보다 앞에 등장해야 합니다.

 

하나의 그래프에는 여러 개의 위상 정렬 결과가 있을 수 있습니다. 그림에서 ABCDEF, ACEDBF, BADCEF, BADFCE 등이 전부 올바른 위상 정렬입니다. 그러나 BFACED는 F가 D보다 먼저 나오기 때문에 잘못된 위상 정렬입니다.

 

만약 그래프 내에 사이클이 존재할 경우에는 올바른 위상 정렬이 존재할 수 없습니다. 주어진 그래프로 예를 들어보면, ABC 중에 그 어떤 것이 먼저 나오더라도 간선으로 주어진 정점 간 선후관계에 모순이 발생하기 때문입니다.

 

그렇기에 위상 정렬은 사이클이 존재하지 않는 방향 그래프에서만 잘 정의됩니다. 사이클이 존재하지 않는 방향 그래프를 DAG(Directed Acyclic Graph)라고 줄여서 부르기도 합니다.

 

위상 정렬에 대해 잘 이해했으니 주어진 그래프에서 위상 정렬을 어떻게 구현할지 생각해봅시다.

 

대충 눈으로 봤을 때 AGCDBEF 와 같은 순서가 보이긴 하지만 이걸 어떤 식으로 구할 수가 있는지 고민이 많이 됩니다.

우리가 위상 정렬을 눈으로 어떻게 알아냈는지 그 과정을 한 번 생각해보고, 코드로 옮겨낼 수 있도록 해보겠습니다.

 

만약 시간이 굉장히 촉박해 머릿속에 지식을 욱여놓고 있는 상황이라면 어쩔 수 없지만, 그렇지 않다면 머릿속으로 대강 떠오른 방식을 바로 코딩이 가능할 정도로 단계를 나누어 깔끔하게 정리를 해 pseudo code 비스무리 한 것을 만들어보는 것도 알고리즘 능력을 끌어올리기 위한 좋은 연습일 것입니다.

 

직접 한 번 해보셨다면 다음 장으로 넘어가봅시다.

 

다른걸 고민하지 말고 위상 정렬 상에서 제일 앞에 오는 원소로 가능한게 무엇일지 먼저 생각해보겠습니다.

 

제일 앞에 오기 위해서는 자신보다 앞에 위치해야 하는 정점이 하나도 없어야 할 것입니다. 이 말은 곧 자신에게 들어오는 간선이 없어야 함을 의미합니다. 예를 들어 그래프에서 A로부터 B로 가는 간선이 있습니다. 그렇기 때문에 B는 A가 나온 다음에야 등장할 수 있고, B는 제일 앞에 올 수 없습니다.

 

자신에게 들어오는 간선이 없다는 것을 indegree가 0이라고 표현을 할 수도 있습니다. indegree는 자신에게 들어오는 간선의 수를 의미합니다. indegree라는 표현이 낯설다면 빠르게 0x0F강 - 그래프에서 indegree와 outdegree를 찾아봅시다.

 

현재의 이 그래프에서는 A, G, C가 가능한 후보군임을 알 수 있습니다.

 

셋 중 어느 것이 제일 앞에 오더라도 전혀 상관이 없겠지만 임의로 A를 택하겠습니다. 위상 정렬에서의 첫 번째 정점은 A가 됩니다.

 

일단 A를 위상 정렬의 제일 앞에 위치시켰습니다. 이제 위상 정렬을 계속 이어나가기 위해 무엇을 해야할까요? A에서 다른 정점으로 나가는 간선을 생각해봅시다. 주어진 그래프에서는 A에서 B로 가는 간선만 존재합니다. A에서 B로 가는 간선은 A가 B보다 먼저 등장해야 한다는 제약 조건을 의미합니다. 그런데 이미 A는 다른 모든 정점들의 앞에 위치했기 때문에 이 제약 조건은 앞으로 신경쓰지 않더라도 자연스럽게 지켜질 것입니다. 이 말은 곧 A를 위상 정렬에 추가한 이후로는 A에서 다른 정점으로 나가는 간선이 의미가 없다는 의미입니다.

 

그렇기에 그냥 주어진 그래프에서 정점 A와 A에서 뻗어나가는 간선을 모두 지운 후, 위상 정렬을 이어나가면 됩니다.

 

정점 A가 제거된 후 B, C, D, E, F, G로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 C, G입니다. 어느 것을 택해도 상관없지만 임의로 C를 택하겠습니다. 위상 정렬에서의 두 번째 원소는 C가 됩니다.

 

마찬가지 논리로 정점 C와 C에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 C가 제거된 후 B, D, E, F, G로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 D, G입니다. C가 사라짐으로서 D가 추가되었네요. 어느 것을 택해도 상관없지만 임의로 D를 택하겠습니다. 위상 정렬에서의 세 번째 원소는 D가 됩니다.

 

정점 D와 D에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 D가 제거된 후에는 그래프가 분리되었습니다. 분리된 것을 신경쓰지 말고 과정을 이어가면 됩니다. B, E, F, G로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 B, G입니다. 어느 것을 택해도 상관없지만 임의로 G를 택하겠습니다. 위상 정렬에서의 네 번째 원소는 G가 됩니다.

 

정점 G와 G에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 G가 제거된 후 B, E, F로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 B, E입니다. 어느 것을 택해도 상관없지만 임의로 E를 택하겠습니다. 위상 정렬에서의 다섯 번째 원소는 E가 됩니다.

 

정점 E와 E에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 E가 제거된 후 B, F로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 B, F입니다. 어느 것을 택해도 상관없지만 임의로 B를 택하겠습니다. 위상 정렬에서의 여섯 번째 원소는 B가 됩니다.

 

정점 E와 E에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 E가 제거된 후 B, F로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 B, F입니다. 어느 것을 택해도 상관없지만 임의로 B를 택하겠습니다. 위상 정렬에서의 여섯 번째 원소는 B가 됩니다.

 

주어진 그래프에서의 위상 정렬이 완료되었습니다. 매 순간마다 들어오는 간선이 없는 정점을 제거함으로서 위상 정렬을 구현할 수 있습니다.

 

엄밀히 말해 우리는 사이클이 존재하지 않는 방향 그래프에서 해당 알고리즘이 늘 올바른 위상 정렬 결과를 내어준다는 점을 증명하지 않았습니다. 이 부분은 곧 사이클이 존재하지 않는 방향 그래프에서 indegree가 0인 정점이 반드시 존재하는지 여부를 확인함으로서 해결할 수 있게 됩니다. 이를 귀류법으로 증명할 수는 있지만 저희는 학부 알고리즘 과목을 수강하는 것이 아니라 코딩테스트에서 써먹을 수 있는 실전 알고리즘을 공부하는 것이기 때문에 생략하도록 하겠습니다.

 

그러니 사이클이 존재하지 않는 방향 그래프에서 해당 알고리즘이 늘 올바른 위상 정렬 결과를 내어준다고 믿고 계속 진행하겠습니다.

 

대충 방법은 알겠는데 이것을 코드로 어떻게 효율적으로 구현할 수 있을까요?

 

위의 구현에서 보면 간선과 정점을 지우고, indegree가 0인 정점을 찾고... 뭔가 많이 복잡해 보입니다.

 

곧이곧대로 구현을 해도 되지만 몇 가지 성질을 잘 집어낸다면 훨씬 더 간편하게, 그리고 더 효율적인 시간복잡도로 구현을 할 수 있게 됩니다.

 

첫 번째 성질은 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 갯수를 저장해두었다가 매번 뻗어나가는 정점들의 indegree 값만 1 감소시켜도 과정을 수행할 수 있다는 성질입니다.

 

두 번째 성질은 indegree가 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가하면 된다는 성질입니다. 목록은 큐로 관리할 계획입니다. 큐 대신 배열이나 스택 등을 활용해도 상관이 없습니다.

 

위상정렬 알고리즘 과정을 글로 정리해보면 위와 같습니다.

 

우선 과정을 눈으로 음미해보세요. 이후 이해를 돕기 위해 준비한 다음 슬라이드들을 확인해보세요.

 

우선 맨 처음 간선을 읽어들이면서 Indegree 배열을 다 채워줍니다. 그리고 큐는 비워둡니다.

 

Indegree 배열을 다 채운 후에는 Indegree가 0인 정점들을 큐에 넣습니다. 이 때 BFS나 DFS에서 하던 것과 같이 visited 방문 체크는 해줄 필요가 없습니다. 과정을 끝까지 보고 나면 이해가 되겠지만 앞으로는 Indegree가 0으로 바뀔 때 큐에 넣을 것이고 각 정점의 Indegree가 0으로 바뀌는 순간은 딱 1번씩 있기 때문입니다.

 

큐의 front에 있는 A를 가져와 위상 정렬 결과에 추가합니다. 정점 A를 "관념적으로" 지울 것이기 때문에 A로부터 연결된 정점 B의 Indegree가 1 감소합니다. 정점 B의 Indegree는 아직 0이 아니기 때문에 큐에 넣지 않습니다.

 

큐의 front에 있는 C를 가져와 위상 정렬 결과에 추가합니다. 정점 C를 "관념적으로" 지울 것이기 때문에 C로부터 연결된 정점 B, D의 Indegree가 1 감소합니다. 정점 B의 Indegree는 아직 0이 아니기 때문에 큐에 넣지 않습니다. 정점 D의 Indegree는 0이 되었기 때문에 큐에 추가해줍니다.

 

큐의 front에 있는 G를 가져와 위상 정렬 결과에 추가합니다. 정점 G를 "관념적으로" 지울 것이기 때문에 G로부터 연결된 정점 E의 Indegree가 1 감소합니다. 정점 E의 Indegree는 아직 0이 아니기 때문에 큐에 넣지 않습니다.

 

큐의 front에 있는 D를 가져와 위상 정렬 결과에 추가합니다. 정점 D를 "관념적으로" 지울 것이기 때문에 D로부터 연결된 정점 B, E의 Indegree가 1 감소합니다. 정점 B, E의 Indegree가 모두 0이 되었기 때문에 큐에 추가해줍니다.

 

큐의 front에 있는 B를 가져와 위상 정렬 결과에 추가합니다. 정점 B를 "관념적으로" 지울 것인데 B로부터 연결된 정점이 없으므로 Indegree의 값은 변화하지 않습니다.

 

큐의 front에 있는 E를 가져와 위상 정렬 결과에 추가합니다. 정점 E를 "관념적으로" 지울 것이기 때문에 G로부터 연결된 정점 F의 Indegree가 1 감소합니다. 정점 F의 Indegree는 0이기 때문에 큐에 추가해줍니다.

 

큐의 front에 있는 F를 가져와 위상 정렬 결과에 추가합니다. 정점 F를 "관념적으로" 지울 것인데 F로부터 연결된 정점이 없으므로 Indegree의 값은 변화하지 않습니다.

 

만약 그래프 내에 사이클이 존재할 경우 이 알고리즘은 어떻게 동작할까요?

 

그림을 재탕했는데요, 그림과 같이 ABC라는 사이클이 있을 경우 A, B, C는 어느 것도 Indegree가 0이 될 수 없습니다. A의 Indegree가 0이 되려면 B의 Indegree가 0이 되어 선택되어야 하는데, B의 Indegree가 0이 되려면 C의 Indegree가 0이 되어 선택되어야 하고, 정작 C의 Indegree가 0이 되려면 A의 Indegree가 0이 되어야 하기 때문에 A, B, C는 서로 물고 물려있기 때문입니다.

 

그렇기에 소개한 알고리즘으로 진행을 한다면 사이클에 포함된 정점은 절대 큐에 들어갈 수가 없게 됩니다. 이 말은 큐가 비어 알고리즘이 종료되었을 때 위상 정렬 결과에 모든 정점이 있지 않다는 얘기입니다. 그러므로 주어진 방향 그래프에 사이클이 있는지 혹은 없는지 여부를 모르더라도 일단 이 알고리즘을 돌리고 나면 위상 정렬 결과에 모든 정점이 포함되어있는지 여부를 확인함으로서 사이클이 있는지 없는지를 확인할 수 있고, 사이클이 없다면 위상 정렬의 결과까지 얻을 수 있습니다.

 

다음 장에는 구현 코드가 나와있습니다. 그런데 다음 장으로 넘기기 전에 직접 한번 구현을 해보시는 것을 추천드립니다.

 

구현 코드를 같이 봅시다. 우선 N개의 정점이 있고 번호는 1-indexed입니다. adj에는 0x0F강 - 그래프에서 배운 것과 같이 나에게서 뻗어나가는 정점의 목록이 저장되어 있습니다. 그리고 indeg에는 각 정점의 indegree가 저장되어 있습니다.

adj, indegree, n은 그래프 정보를 입력받을 때 미리 값을 다 넣어야 합니다. 미리 값을 어떻게 넣어둔다는 것인지 헷갈린다면 조금 있다가 실제 문제에 대한 풀이를 보면 도움이 될 것입니다.

 

코드의 흐름은 위에서 설명한 것과 판박이입니다. 이 때 C++11 이상이 지원될 경우 12, 13번 줄을 for(auto nxt : adj[cur])로 한 줄에 쓸 수 있습니다.

 

result에는 위상 정렬 결과가 저장되고 result의 길이가 n인지 여부를 통해 사이클이 있는지 판단할 수 있습니다.

 

이 알고리즘의 시간복잡도는 얼마일까요? 각 정점은 큐에 최대 1번 들어가고 indegree를 감소시키는 연산은 각 간선에 대해 딱 1번씩만 발생하기 때문에 시간복잡도는 $O(V+E)$입니다. 그래프에서의 BFS/DFS가 $O(V+E)$인 것과 비슷한 맥락입니다.

 

첫 번째 문제는 BOJ 2252번: 줄 세우기 입니다. 문제 상황을 살펴보면 그냥 대놓고 각 학생을 정점으로 뒀을 때의 그래프에서 위상 정렬을 수행하는 문제임을 알 수 있습니다. 전체 코드는 링크를 참조하시고, 입력을 어떻게 처리하는지만 한 번 짚고 가봅시다.

 

크게 어려울 것 없이 a에서 b로 가는 간선이 주어질 때, adj[a]에는 b를 추가하고 indeg[b]는 1 증가시켜주기만 하면 모든 준비가 끝납니다.

 

지금까지 배운 것을 잘 조합하면 충분히 혼자 힘으로 풀어낼 수 있으니 정답 코드를 보기 전에 직접 맞춰봅시다!!

 

연습 문제로는 적절한 아이디어로 그래프를 잘 구성해야 하는 BOJ 2623번: 음악프로그램 문제, 위상 정렬 그래프에서 DP를 해야 하는 BOJ 1005번: ACM Craft 문제를 두었습니다. 응용이 필요하기 때문에 많이 어려울 수 있습니다. 일단 시도를 해보시고, 해결법을 잘 모르겠고 다른 사람들의 풀이를 이해하는 것에도 어려움을 느낀다면 넘어가셔도 무방합니다.

 

이번 강의에서는 위상 정렬을 익혔습니다. 코딩테스트에서 그다지 많이 나오지 않는 유형이지만 구현이 그다지 어렵지 않은 편입니다. 문제에서 원소 간의 선후 관계가 주어지고 순서를 정해야 하는 상황이면 앞으로는 이번 강의에서 배운 위상 정렬을 떠올려 해결해봅시다. 고생 많으셨습니다!!