[실전 알고리즘] 0x1A강 - 위상 정렬

 

 

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

 

위상 정렬이 무엇인지도 소개해드릴거고 구현과 연습 문제도 다룰 예정입니다.

 

위상 정렬의 본격적인 정의를 배워보기 전에 실생활의 쉬운 예시를 들어 설명을 해보겠습니다.

 

가장 실생활에서 찾기 쉬운 예시는 바로 교과 이수 제도입니다. 대학교에는 선수 과목이 있는 과목들이 있습니다. 예를 들어 프로그래밍1 과목을 들어야 프로그래밍2 과목을 들을 수 있게 해놓은 것과 같은 상황을 생각해볼 수 있습니다.

 

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

 

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

 

그러나 선수 과목을 지켜야하기 때문에 아무리 이산수학을 미루고 싶어도 알고리즘을 먼저 듣고 이산수학을 그 다음에 듣는 것은 불가능합니다. 이산수학을 안듣고 알고리즘을 수강신청하면 알고리즘 수업을 들으러 갈 때 교수님이 이놈 하고 혼냅니다.

 

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

 

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

 

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

 

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

 

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

 

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

 

대충 눈으로 봤을 때 AGCDBEF와 같은 순서가 보이긴 하지만 이걸 어떤 식으로 구할 수가 있는지 고민이 많이 됩니다. 뭐 예를 들어서 AGCDBEF를 어떻게 알아냈는지 그 과정을 한 번 생각해보고 코드로 작성해보겠습니다.

 

만약 시간이 굉장히 촉박하면 어쩔 수 없지만 머릿속으로 대강 떠오른 방식을 바로 코딩이 가능할 정도로 단계를 나누어 깔끔하게 정리를 해 코드를 만들어보는 것도 알고리즘 능력을 끌어올리기 위한 좋은 연습입니다.

 

직접 한 번 해보셨다면 다음 슬라이드로 넘어가봅시다.

 

다른건 고민하지 말고 일단은 위상 정렬 상에서 제일 앞에 오는 원소로 가능한게 무엇인지를 먼저 생각해보겠습니다. 제일 앞에 오기 위해서는 자신보다 앞에 위치해야 하는 정점이 하나도 없어야합니다. 이 말은 곧 자신에게 들어오는 간선이 없어야 함을 의미합니다. 예를 들어 그래프에서 A로부터 B로 가는 간선을 생각해보겠습니다. 이 간선이 나타내는 바가 무엇인지 생각해보면 B는 A가 나온 다음에야 등장할 수 있다는 것을 나타냅니다. 그렇기 때문에 B는 제일 앞에 올 수 없습니다.

 

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

 

현재의 이 그래프에서 indegree가 0인 정점이 무엇인가 살펴보면 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입니다.

 

정점 B와 B에서 뻗어나가는 간선을 모두 지웠습니다. 정점 B가 제거된 후에는 F만 남았습니다. 자연스럽게 위상 정렬에서의 일곱 번째 원소는 F입니다.

 

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

 

엄밀히 말해 우리는 사이클이 존재하지 않는 방향 그래프에서 해당 알고리즘이 늘 올바른 위상 정렬 결과를 내어준다는 점을 증명하지 않았습니다. 구체적으로 매 순간마다 indegree가 0인 정점이 항상 존재한다는걸 증명할 필요가 있습니다. 이 부분은 귀류법으로 증명할 수 있고 그렇게까지 어려운 내용이 아니긴 하지만 설명은 생략하도록 하겠습니다. 이런 엄밀함에 관심이 많으시다면 직접 증명을 시도해보셔도 좋습니다.

 

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

 

방법은 같이 살펴봐서 대강 알겠는데 이것을 코드로 어떻게 효율적으로 구현할 수 있을까요? 위의 구현에서 보면 간선과 정점을 지우고, indegree가 0인 정점을 찾아야 하는 일련의 과정이 뭔가 많이 복잡해 보입니다. 이걸 곧이곧대로 구현을 해도 되긴 한데 그렇게 구현을 하면 아마 대부분 O(V²)에 동작하는 코드를 작성하게 될 가능성이 큽니다. 몇 가지 성질을 잘 집어낸다면 훨씬 더 간편하게, 그리고 O(V+E)라는 더 효율적인 시간복잡도로 구현을 할 수 있게 됩니다.

 

첫 번째로, 앞에서는 정점과 간선을 지웠지만 사실은 실제로 지울 필요 없이 미리 indegree의 값을 저장했다가 매번 뻗어나가는 정점들의 indegree 값만 1 감소시켜도 과정을 수행할 수 있습니다.

 

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

 

앞에서 설명한 성질들을 이용해 효율적으로 동작하는 위상 정렬 알고리즘 과정을 글로 정리해보면 위와 같습니다. 우선 과정을 눈으로 음미해봅시다. 이후 이해를 돕기 위해 준비한 다음 슬라이드들을 확인해보도록 합시다.

 

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

 

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

 

큐의 front에 있는 A를 가져와 위상 정렬 결과에 추가합니다. 실제로 정점 A와 A에서 B로 가는 간선을 지우는 대신에 정점 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를 관념적으로 지울 것이기 때문에 E로부터 연결된 정점 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에는 나에게서 뻗어나가는 정점의 목록이 저장되어 있습니다. 방향 그래프에서의 인접 리스트를 이용한 그래프 저장 방법이라고 생각하면 됩니다. 그리고 deg에는 각 정점의 indegree가 저장되어 있습니다.

 

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

 

코드의 흐름은 위에서 설명한 것과 판박이입니다. 최종적으로 result에는 위상 정렬 결과가 저장되고 result의 길이가 n인지 여부를 통해 사이클이 있는지 판단할 수 있습니다.

 

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

 

다음으로 연습 문제를 풀어보겠습니다. 다룰 연습 문제는 BOJ 2252번: 줄 세우기 입니다. 문제 상황을 살펴보면 그냥 대놓고 각 학생을 정점으로 뒀을 때의 그래프에서 위상 정렬을 수행하는 문제임을 알 수 있습니다. 위상 정렬 방법은 앞에서 설명을 했으니 입력을 어떻게 처리하면 될지만 고민하면 되는데 이것 또한 그래프 단원에서 많이 해본 일이어서 충분히 할만할 것 같습니다. 지금까지 배운 것을 잘 조합하면 충분히 혼자 힘으로 풀어낼 수 있으니 정답 코드를 보기 전에 직접 도전해보세요. 코드는 아래에서 확인할 수 있습니다.

 

크게 어려울 것 없이 a에서 b로 가는 간선이 주어질 때 adj[a]에는 b를 추가하고 deg[b]는 1 증가시켜주기만 하면 모든 준비가 끝납니다. 이후 위상 정렬을 수행하면 됩니다. (코드)

 

이번 강의의 내용을 간략하게 정리해보면 위상 정렬을 익혔고 사이클이 없는 방향 그래프에서만 올바른 위상 정렬이 존재한다는 사실 또한 알게 되었습니다. 위상 정렬이 코딩테스트에서 그렇게 잘 나오는 유형이라고 할 수는 없지만 구현이나 개념이 그다지 어렵지 않은 편이니 문제에서 원소 간의 선후 관계가 주어지고 순서를 정해야 하는 상황이면 앞으로는 이번 강의에서 배운 위상 정렬을 떠올려볼 수 있도록 합시다.

 

한편으로 위상 정렬의 아주 유명한 응용 중에 위상 정렬 dp가 있습니다. 위상 정렬만 해도 충분한 난이도라고 생각이 들어 강의 내에서는 위상 정렬 dp를 다루지 않지만 위상 정렬을 큰 어려움 없이 이해했고 dp도 자신 있다면 연습 문제를 통해 위상 정렬 dp를 학습해보셔도 괜찮습니다.