[실전 알고리즘] 0x12강 - 최소 신장 트리_구버전

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

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

 

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

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

 

안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 엄밀히 말해 0x0A강 - 그리디 이후로는 딱히 삼성전자 역량테스트 A형에 나올만한 유형이 아니긴한데, 지금 다룰 최소 신장 트리는 2019년에 한 번 출제된 적이 있습니다. BOJ에는 17472번: 다리 만들기 2 라는 이름으로 복원되어 있습니다. 해당 문제의 경우 간선의 수가 적어 최소 신장 트리에 대한 기초적인 지식을 알고 있었다면 굳이 최소 신장 트리를 효율적으로 구할 수 있는 Prim 혹은 Kruskal 알고리즘을 모르더라도 전수 조사를 통해 답을 구할 수 있긴 했습니다.

 

앞으로 있을 삼성전자 역량테스트 A형 시험에서도 BFS/DFS/백트래킹/시뮬레이션/전수조사를 통해 해결할 수 있는 문제만 출제될 것으로 추정이 되지만 고급개념을 알면 풀이에 대한 접근을 더 쉽게 할 수 있는 문제가 충분히 나올 수 있으니 당장 필요없는 것 같아 보이더라도 시간이 남으면 상위 개념들을 공부해두는 것이 좋다고 생각합니다. 그리고 삼성만을 목표로 두지 않고 카카오, 네이버, LG 등의 다양한 회사의 코딩테스트도 응시할 계획이 있다면 이들의 출제 경향을 예측하기 힘드니 당연히 필요하구요.

 

최소 신장 트리(Minimum Spanning Tree)를 다루기 전에 신장 트리가 무엇인지 알아봅시다.  신장 트리는 주어진 방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리를 의미합니다. 서브그래프는 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프를 의미합니다. 신장 트리의 정의를 그냥 읽었을 때에는 무슨 소리인가 싶은데 그림을 보면 명확하게 이해가 갈 것입니다.

 

왼쪽과 같은 그래프가 있을 때, 오른쪽에 있는 그래프들은 전부 왼쪽 그래프의 신장 트리입니다. 일단 모든 정점을 포함한 서브그래프이고, 트리이기 때문입니다. 트리는 0x0F강 - 트리에서 배웠듯 사이클이 없고 연결된 그래프입니다.

 

트리의 성질로부터 주어진 그래프의 정점이 $V$개일 때 신장 트리는 $V-1$개의 간선을 가지고 있음을 알 수 있습니다. 그리고 상식적으로 생각했을 때 주어진 그래프가 연결 그래프일 때만 신장 트리가 존재함을 알 수 있을 것입니다.

 

반면 지금 슬라이드에서 오른쪽에 있는 그래프들은 전부 신장 트리가 아닙니다. 첫 번째 그래프는 가운데 정점이 연결되지 않아 연결그래프여야 한다는 트리의 조건이 위배되어 신장 트리가 아니고, 두, 세 번째 그래프는 사이클이 존재하기 때문에 신장 트리가 아닙니다. 네 번째 그래프는 원래 그래프에 없던 간선이 등장해서 아예 서브그래프가 아니기 때문에 신장 트리가 아닙니다.

 

그리고 최소 신장 트리는 신장 트리 중에서 간선의 합이 최소인 트리를 의미합니다. 주어진 그래프에는 지금 그림으로 표현한 4개의 신장 트리 이외에도 훨씬 더 많은 신장 트리들이 존재합니다. 이들 중에서 최소 신장 트리는 간선의 합이 15인 신장 트리입니다. 오른쪽에 나타낸 예시 중에서는 첫 번째와 세 번째의 신장 트리가 최소 신장 트리입니다. 두 번째와 네 번째의 신장 트리는 간선의 합이 각각 18과 16으로 간선의 합이 더 작은 신장 트리가 존재하기 때문에 최소 신장 트리가 아닙니다.

 

이번 예시에서 알 수 있듯 최소 신장 트리는 동일한 그래프에서 딱 한 개로 정해지지 않고 여러 개일 수 있습니다.

 

최소 신장 트리를 구하는 첫 번째 방법인 크루스칼(Kruskal) 알고리즘을 알아봅시다. 미리 안타까운 소식을 알려드리자면 크루스칼 알고리즘은 Union-Find라는 알고리즘을 모르면 효율적으로 구현할 수 없습니다. 그리고 union find 알고리즘이 엄청 난이도가 있는 것은 아니지만 코딩테스트에서 다룰 필요가 있지는 않다고 생각해 Union-Find 알고리즘은 따로 설명하지 않을 예정입니다. 그렇기에 크루스칼 알고리즘이 무엇인지는 알려드릴 것이지만 실제 구현 코드는 Union-Find를 모를 경우 이해할 수 없습니다.

 

크루스칼 알고리즘은 union find 알고리즘을 알고 있다고 가정할 때 프림 알고리즘보다 구현이 쉬운 알고리즘입니다. 설령 union find 알고리즘을 모른다고 하더라도 크루스칼 알고리즘이 무엇인지는 알고 있는 것이 좋다고 생각하기에 가능하면 이 장을 뛰어넘지 않으면 좋겠지만 시간이 없고 단지 최소 신장 트리의 구현법만이 궁금한 경우에는 크루스칼 알고리즘을 뛰어넘고 프림 알고리즘으로 바로 가셔도 됩니다.

 

크루스칼 알고리즘은 가장 비용이 낮은 간선부터 시작해 서로 떨어져 있던 정점들을 합쳐나가며 총 $V-1$개의 간선을 택하는 알고리즘입니다. 과정을 글로 나타내면

 

1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다.

2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 하자. 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어간다. u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다.

3. 최소 신장 트리에 $V-1$개의 간선을 추가시켰다면 과정을 종료한다. 그렇지 않다면 그 다음으로 비용이 큰 간선을 선택한 후 2, 3번 과정을 반복한다.

 

입니다. 이 설명에서 "같은 그룹으로 만든다"라는 표현이 잘 이해가 가지 않을 것 같습니다. 걱정하지 말고 같이 과정을 살펴봅시다.

 

알고리즘을 시작해봅시다. 우선 그룹은 정점의 색깔로 표현하겠습니다. 맨 처음 모든 정점은 그룹이 다릅니다.

 

간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택합니다. 실제 코드로 구현할 때에는 간선을 크기 순으로 선택하기 위해 정렬 과정이 필요하겠지만 예시로 설명할 때에는 그냥 저희가 충분히 눈으로 보고 작은 것 부터 고를 수 있으니 정렬 과정을 생략하겠습니다.

 

비용이 가장 작은 간선은 비용이 3인 간선입니다. 3인 간선은 3개가 있지만 그 중 아무거나 택해도 상관 없습니다. 임의로 1과 4를 연결하는 간선을 택하겠습니다. 색에서 알 수 있듯 1과 4는 그룹이 다릅니다. 그렇기 때문에 같은 그룹으로 만들고 1과 4를 연결하는 간선을 최소 신장 트리에 추가합니다.

 

그 다음으로 비용이 가장 작은 간선은 여전히 비용이 3인 간선입니다. 3인 간선은 1과 3을 연결하는 간선, 3과 4를 연결하는 간선 2개가 있지만 그 중 아무거나 택해도 상관 없습니다. 임의로 1과 3을 연결하는 간선을 택하겠습니다. 색에서 알 수 있듯 1과 3는 그룹이 다릅니다. 그렇기 때문에 같은 그룹으로 만들고 1과 4를 연결하는 간선을 최소 신장 트리에 추가합니다.

 

그 다음으로 비용이 가장 작은 간선은 여전히 비용이 3인 간선입니다. 이제 3인 간선은 3과 4를 연결하는 간선만 남았습니다. 3과 4을 연결하는 간선을 택하겠습니다. 색에서 알 수 있듯 3과 4는 그룹이 동일합니다. 그렇기 때문에 아무 것도 하지 않고 넘어갑니다. 당연히 이 간선은 최소 신장 트리에 추가되지 않습니다.

 

그 다음으로 비용이 가장 작은 간선은 비용이 4인 간선입니다. 1과 2를 연결하는 간선을 택하겠습니다. 색에서 알 수 있듯 1과 2는 그룹이 다릅니다. 그렇기 때문에 같은 그룹으로 만들고 1과 2를 연결하는 간선을 최소 신장 트리에 추가합니다.

 

그 다음으로 비용이 가장 작은 간선은 비용이 5인 간선입니다. 3과 5를 연결하는 간선을 택하겠습니다. 색에서 알 수 있듯 3과 5는 그룹이 다릅니다. 그렇기 때문에 같은 그룹으로 만들고 1과 2를 연결하는 간선을 최소 신장 트리에 추가합니다.

 

정점이 총 5개인데 4개의 간선을 최소 신장 트리에 추가시켰습니다. 그러므로 최소 신장 트리를 만들어내는데 성공했고 알고리즘은 종료됩니다.

 

크루스칼 알고리즘의 과정을 잘 이해했다면 이 알고리즘은 그냥 사이클을 만들어내지 않는 선에서 비용이 작은 간선부터 최소 신장 트리에 편입시키는 그리디 알고리즘임을 알 수 있습니다. 문제는 이 알고리즘의 정당성이 썩 직관적으로 와닿지 않는 분도 있을 것입니다. 당장 최소인 간선을 택하지 않았을 때 길게 봐서는 더 이득일 수 있을 것 같기도 하고...

 

결론적으로 말해서 이 알고리즘의 정당성, 즉 반드시 최소 신장 트리를 반환하는 사실은 귀납법을 이용해 깡으로 증명하거나 매트로이드라는 개념을 빌려와 조금 더 쉽게 설명할 수 있습니다. 그러나 증명이 많이 복잡하고 적어도 제 상식으로는 코딩테스트를 대비하는 취준생 중에서 이 증명을 할 수 있는 사람은 아무리 많이 쳐줘도 1%가 될까말까이기 때문에 그래프 이론이나 알고리즘을 전공하고자 하는게 아니면 굳이 알 필요는 없다고 생각합니다. 그렇기에 증명은 생략합니다.

 

그런데 "특정 두 정점이 같은 그룹인지 다른 그룹인지"를 어떻게 판단할 수 있을까요? 현재 우리가 배운 내용만을 가지고 판단하는 방법을 한 번 고민해봅시다.

 

바로 Flood Fill을 이용해 해결할 수 있습니다. 최소 신장 트리에 편입시킨 간선을 별도로 관리하고 있다고 할 때 정점 A와 B가 같은 그룹인지 판단하려면 A에서 B로 갈 수 있는지, 즉 A에서 Flood Fill을 돌려 B를 방문하는지 확인하면 됩니다. 그런데 이 과정에서 필요한 시간복잡도는 $O(V)$ 입니다. 그렇기 때문에 Flood Fill을 이용해 크루스칼 알고리즘을 구현할 경우 간선의 정렬에서 $O(ElgE)$, 이후 최대 $E$번에 걸쳐 같은 그룹인지 판단하는 과정이 필요하므로 $O(VE)$가 필요해 최종 시간복잡도는 $O(ElgE + VE)$가 되어 많이 비효율적입니다.

 

대신 Union-Find를 사용할 경우 "특정 두 정점이 같은 그룹인지 다른 그룹인지"를 사실상 상수 시간에 확인할 수 있습니다. 정확히는 아커만 함수(Ackermann Function)의 값이 계수로 붙긴 하지만 이 함수의 값은 $N$이 $2^{65536}$일 때 비로소 5가 될 정도로 아주 작은 값을 가지는 함수이기 때문에 상수 시간이라고 생각하셔도 무방합니다. Union-Find를 이용해서 크루스칼 알고리즘을 구현하면 $O(ElgE)$로 해결이 가능합니다.

 

일단 "특정 두 정점이 같은 그룹인지 다른 그룹인지"는 is_diff_group 이라는 함수에서 처리해준다고 생각하고 코드를 봅시다. 이 함수는 Flood Fill로도, Union-Find로도 구현할 수 있지만 Union-Find로 구현해야 더 효율적인 시간복잡도로 최소 신장 트리를 구할 수 있습니다.

 

이전 강의들에서는 간선을 vector<int> adj[10]에 저장했는데 크루스칼 알고리즘에서는 간선을 크기 순으로 정렬하는 과정이 필요하기 때문에 전부 tuple<int,int,int> edge 배열에 저장해둡니다. tuple의 정렬은 제일 앞의 값부터 비교해서 이루어지므로 cost, vertex1, vertex2 순으로 담아둡니다.

 

e개의 간선을 크기 순으로 살펴보며 해당 간선의 정점 두 개가 다른 그룹인지, 같은 그룹인지 확인합니다. 같은 그룹이라면 넘어가고, 다른 그룹이라면 간선을 출력한 뒤 cnt를 1 증가시켜줍니다. 최소 신장 트리는 v-1개의 간선으로 이루어져있으므로 cnt가 v-1이 되는 순간 과정은 종료됩니다.

 

tuple은 C++11부터 사용할 수 있는 자료형입니다. 만약 C++11이 지원되지 않는 코딩테스트에 응시할 경우에는 직접 구조체와 비교 연산자를 설정할 수도 있지만 저는 pair<int, pair<int, int> > 를 사용하는 것을 선호합니다. 단지 간선을 저장하는 type이 달라질 뿐 전반적인 코드의 흐름은 큰 차이가 없습니다. 우측의 코드를 확인해보세요.

 

어차피 프림 알고리즘 장으로 가면 지금까지 강의에서 다룬 내용만으로도 구현할 수 있는 $O(ElgE)$ 알고리즘을 소개할 것이기 때문에 $O(ElgE + VE)$ 시간복잡도의 알고리즘은 필요는 없다고 생각합니다. 그래서 Union-Find를 사용한 크루스칼 알고리즘을 알려드릴테니 Union-Find를 알고 계시거나 따로 공부할 의향이 있으시면 확인해보시고, 그렇지 않을 경우 넘어가시면 됩니다.

 

BOJ 1197번: 최소 스패닝 트리 문제는 단순히 주어진 그래프에서 최소 신장 트리의 간선의 합을 구하는 문제입니다. 실제로 is_diff_group까지 메꾼 전체 코드를 확인해봅시다.

 

어차피 프림 알고리즘 장으로 가면 지금까지 강의에서 다룬 내용만으로도 구현할 수 있는 $O(ElgE)$ 알고리즘을 소개할 것입니다. 그렇기 때문에 is_diff_group을 Flood Fill로 구현한 $O(ElgE + VE)$ 시간복잡도의 알고리즘을 굳이 다루고 갈 필요가 없다고 생각합니다. 그래서 Union-Find를 사용한 크루스칼 알고리즘을 알려드릴테니 Union-Find를 알고 계시거나 따로 공부할 의향이 있으시면 확인해보시고, 그렇지 않을 경우 넘어가시면 됩니다.

 

이 문제에서는 단순히 간선의 합만 계산하면 되기 때문에 간선을 찾아낸 후에는 다른 처리 없이 ans에 cost를 더했습니다. 이해를 돕기 위해 is_diff_group 이라는 함수명으로 써놓았지만 Union-Find를 이전에 공부했다면 해당 과정이 union임을 알 수 있을 것입니다. Union-by-rank를 하기 위해 union 부분의 코드가 다소 난잡해졌는데, 꼭 Union-by-rank를 하지 않고 그저 경로 압축만 진행하더라도 대략 로그 스케일로 떨어져서 문제를 통과하는데 큰 무리가 없습니다.

 

최소 신장 트리를 구하는 두 번째 방법인 프림(Prim) 알고리즘을 알아봅시다. 프림 알고리즘은 Union-Find 같은 것을 몰라도 구현할 수 있습니다!! 그렇지만 크루스칼 알고리즘에 비해 구현이 조금 어려운 편입니다. 그래도 엄청 어렵지는 않아요.

 

크루스칼 알고리즘이 가장 비용이 낮은 간선부터 시작해 서로 떨어져 있던 정점들을 합쳐나가며 총 $V-1$개의 간선을 택하는 알고리즘이었다면, 프림 알고리즘은 한 정점에서 시작해 확장해나가는 알고리즘입니다. 글로 읽었을 때 충분히 이해가 갈 것 같습니다.

 

1. 하나의 정점을 선택해 최소 신장 트리에 추가한다.

2. 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가한다. 해당 간선의 최소 신장 트리에 포함되지 않은 정점 또한 최소 신장 트리에 추가한다.

3. 최소 신장 트리에 V-1개의 간선이 추가될 때 까지 2번 과정을 반복한다.

 

프림 알고리즘 또한 해당 알고리즘이 왜 최소 신장 트리를 반환하는지를 증명하는 것이 어렵습니다. 그러니 아쉽지만 증명은 건너뛰도록 하겠습니다.

 

이제 같이 프림 알고리즘의 과정을 살펴봅시다.

 

알고리즘을 시작해봅시다. 우선 하나의 정점을 잡아 최소 신장 트리에 추가해야 합니다. 아무거나 잡아도 상관이 없지만 임의로 1번 정점을 선택하겠습니다.

 

현재 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선은 1과 2를 연결하는 간선, 1과 3을 연결하는 간선, 1과 4를 연결하는 간선 총 3개가 있습니다. 이 3개 중에서 비용이 가장 낮은 간선은 비용이 3인 1과 3을 연결하는 간선 혹은 1과 4를 연결하는 간선인데, 임의로 1과 3을 연결하는 간선을 택하겠습니다.

 

1과 3을 연결하는 간선을 택했기 때문에 해당 간선과 3번 정점이 최소 신장 트리에 추가됩니다.

 

현재 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선은 1과 2, 1과 4, 3과 4, 3과 5를 연결하는 간선으로 총 4개입니다. 이들 중에서 비용이 가장 낮은 간선은 비용이 3인 1과 4을 연결하는 간선 혹은 3과 4를 연결하는 간선인데, 임의로 3과 4를 연결하는 간선을 택하겠습니다.

 

3과 4를 연결하는 간선을 택했기 때문에 해당 간선과 4번 정점이 최소 신장 트리에 추가됩니다.

 

현재 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선은 1과 2, 3과 5, 4과 5를 연결하는 간선으로 총 3개입니다. 이들 중에서 비용이 가장 낮은 간선은 비용이 4인 1과 2를 연결하는 간선입니다. 이 간선을 택하겠습니다.

 

1과 2를 연결하는 간선을 택했기 때문에 해당 간선과 2번 정점이 최소 신장 트리에 추가됩니다.

 

현재 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선은 2와 5, 3과 5, 4과 5를 연결하는 간선으로 총 3개입니다. 이들 중에서 비용이 가장 낮은 간선은 비용이 5인 3과 5를 연결하는 간선입니다. 이 간선을 택하겠습니다.

 

3과 5를 연결하는 간선을 택했기 때문에 해당 간선과 5번 정점이 최소 신장 트리에 추가됩니다.

 

정점이 총 5개인데 4개의 간선을 최소 신장 트리에 추가시켰습니다. 그러므로 최소 신장 트리를 만들어내는데 성공했고 알고리즘은 종료됩니다.

 

과정을 잘 따라오셨다면 1번 정점에서 시작해 매번 가장 낮은 비용의 간선을 찾아 점점 뻗어나가는 모양임을 알 수 있습니다.

 

방법 자체는 크게 어렵지 않게 이해하실 수 있을 것 같은데, 진짜 문제는 프림 알고리즘의 구현입니다. 과연 이 알고리즘을 어떻게 구현해야 할까요?

 

우리가 대충 손으로 했던 방법 그대로 구현하려고 한다면 $V-1$번에 걸쳐 현재 최소 간선 트리에 포함된 정점과 그렇지 않은 정점을 연결하는 모든 간선을 조사하고 이들 중에서 최소 비용인 간선을 택하는 방식으로 구현이 이루어질 것입니다. 안타깝게도 이 구현은 아주 비효율적입니다.

 

프림 알고리즘을 효율적으로 구현하기 위해서는 힙이 필요합니다. 힙을 0x0D강 - 해쉬, 이진 검색 트리, 힙에서 다뤘는데 기억나시나요? 힙(Heap)은 원소의 삽입과 최댓값(혹은 최솟값) 확인 및 삭제를 모두 $O(lgN)$에 수행할 수 있는 자료구조입니다. 만약 기억이 나지 않는다면 0x0D강에서 힙을 꼭 다시 보고 오세요.

 

힙에 간선들을 적절히 넣어두면 매 순간마다 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중에서 최소를 효율적으로 알아낼 수 있습니다.

 

실제 구현에 초점을 맞춘 프림 알고리즘을 다시 소개하겠습니다. 프림 알고리즘은 구체적으로

 

1. 하나의 정점을 선택해 최소 신장 트리에 추가하고 해당 정점과 연결된 모든 간선을 힙에 추가한다.

2. 힙에서 비용이 가장 작은 간선을 꺼낸다.

3-1. 만약 해당 간선이 최소 신장 트리에 포함된 두 정점을 연결한다면 아무 것도 하지 않고 넘어간다.

3-2. 해당 간선이 최소 신장 트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 우선 해당 간선과 정점 v를 최소 신장 트리에 추가한다. 그리고 정점 v과 최소 신장 트리에 포함되지 않는 정점을 연결하는 모든 간선을 힙에 추가한다.

4. 최소 신장 트리에 V-1개의 간선이 추가될 때 까지 2, 3번 과정을 반복한다.

 

라는 절차에 따라 구현이 이루어집니다. 이 절차에 따른 과정을 다시 확인해봅시다.

 

알고리즘을 시작해봅시다. 우선 하나의 정점을 잡아 최소 신장 트리에 추가해야 합니다. 아무거나 잡아도 상관이 없지만 임의로 1번 정점을 선택하겠습니다.

 

1번 정점과 연결된 간선은 1과 2, 1과 3, 1과 4를 연결하는 간선으로 총 3개가 있습니다. 2, 3, 4번 정점은 모두 최소 신장 트리에 포함되지 않은 정점이므로 3개 간선을 전부 힙에 추가합니다.

 

엄밀히 말해 힙은 이진 트리 형태로 구현이 이루어지지만 지금 힙의 동작 원리에 관심이 있는 것이 아니므로 힙의 정상적인 구조를 따르지 않고 배열의 형태로 표현하겠습니다.

 

현재 힙에서 비용이 가장 작은 간선은 1과 3을 연결하는 간선 혹은 1과 4를 연결하는 간선입니다. 임의로 1과 3을 연결하는 간선을 꺼내겠습니다. 꺼내면서 자연스럽게 힙에서 제거됩니다.

 

이 간선은 최소 신장 트리에 포함된 1번 정점과 포함되지 않은 3번 정점을 연결한 간선입니다. 그러므로 해당 간선과 3번 정점을 최소 신장 트리에 추가하고 3번 정점을 선택합니다.

 

3번 정점과 연결된 간선은 3과 4, 3과 5, 3과 1을 연결하는 간선으로 총 3개가 있습니다. 1, 4, 5번 정점 중에서 1번 정점은 최소 신장 트리에 이미 포함된 간선이므로 3과 4, 3과 5를 연결하는 간선만 힙에 추가합니다.

 

현재 힙에서 비용이 가장 작은 간선은 1과 3을 연결하는 간선 혹은 3과 4를 연결하는 간선입니다. 임의로 3과 4를 연결하는 간선을 꺼내겠습니다. 꺼내면서 자연스럽게 힙에서 제거됩니다.

 

이 간선은 최소 신장 트리에 포함된 정점 3과 포함되지 않은 정점 4을 연결한 간선입니다. 그러므로 해당 간선과 4번 정점을 최소 신장 트리에 추가하고 4번 정점을 선택합니다.

 

4번 정점과 연결된 간선은 1과 4, 3과 4, 4과 5를 연결하는 간선으로 총 3개가 있습니다. 1, 4, 5번 정점 중에서 1, 3번 정점은 최소 신장 트리에 이미 포함된 간선이므로 4와 5를 연결하는 간선만 힙에 추가합니다.

 

현재 힙에서 비용이 가장 작은 간선은 1과 4을 연결하는 간선입니다. 이 간선을 꺼내겠습니다. 꺼내면서 자연스럽게 힙에서 제거됩니다.

 

이 간선은 최소 신장 트리에 포함된 1번 정점과 4번 정점을 연결한 간선입니다. 그러므로 아무 것도 하지 않고 넘어갑니다.

 

현재 힙에서 비용이 가장 작은 간선은 1과 2을 연결하는 간선입니다. 이 간선을 꺼내겠습니다. 꺼내면서 자연스럽게 힙에서 제거됩니다.

 

이 간선은 최소 신장 트리에 포함된 1번 정점과 포함되지 않은 2번 정점을 연결한 간선입니다. 그러므로 해당 간선과 2번 정점을 최소 신장 트리에 추가하고 2번 정점을 선택합니다.

 

2번 정점과 연결된 간선은 1과 2, 2와 5를 연결하는 간선으로 총 2개가 있습니다. 1, 5번 정점 중에서 1번 정점은 최소 신장 트리에 이미 포함된 간선이므로 2와 5를 연결하는 간선만 힙에 추가합니다.

 

현재 힙에서 비용이 가장 작은 간선은 3과 5를 연결하는 간선입니다. 이 간선을 꺼내겠습니다. 꺼내면서 자연스럽게 힙에서 제거됩니다.

 

이 간선은 최소 신장 트리에 포함된 2번 정점과 포함되지 않은 5번 정점을 연결한 간선입니다. 그러므로 해당 간선과 5번 정점을 최소 신장 트리에 추가하고 5번 정점을 선택합니다.

 

정점이 총 5개인데 4개의 간선을 최소 신장 트리에 추가시켰습니다. 그러므로 최소 신장 트리를 만들어내는데 성공했고 알고리즘은 종료됩니다.

 

맨 처음 대략적인 설명을 들을 땐 쉬웠는데 힙이 들어간 실제 구현 파트가 까다롭게 느껴질 것 같습니다. 다소 난해하지만 이 알고리즘의 흐름이 다음 다음 강에서 다루게 될 다익스트라 알고리즘과 매우 유사하기 때문에 지금 이해를 잘 하고 넘어가면 다익스트라 알고리즘을 날로 먹을 수 있게 됩니다.

 

코드로 구현하면 이와 같습니다. using은 모던 C++에서 typedef를 대신해 사용하는 문법인데 그냥 priority_queue의 선언에서 tuple<int, int, int>를 매번 쓰기가 싫어 이용했습니다. adj는 이전과 달리 간선의 cost와 정점 번호 2개를 pair로 들고 있습니다. 간선의 비용 정보가 필요해서 이렇게 두었습니다. chk[i]는 i번째 정점이 최소 신장 트리에 포함되었는지 여부를 저장하는 변수입니다.

 

priority_queue는 기본적으로 max heap(최댓값을 확인/삭제할 수 있는 힙)인데 최소 신장 트리에서는 min heap이 필요하므로 08번 줄과 같이 선언했습니다. PQ에 값을 넣을 때 현재 최소 신장 트리에 속하지 않은 정점의 번호를 제일 마지막에 가도록 했기 때문에 chk[v1]은 반드시 참입니다. 그러므로 현재 보고 있는 간선이 최소 신장 트리에 포함된 두 정점을 연결한 것인지, 최소 신장 트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한 것인지 판단하기 위해서는 15번 줄과 같이 chk[v2]만 확인하면 됩니다.

 

나름대로 설명을 한다고는 했는데 아직 STL이 친숙하지 않다면 여러모로 외계어만 잔뜩 써진 것 같고 이해가 잘 가지 않을 것 같습니다. 그래도 한 줄씩 뜯어서 보면 엄청 어려운 것은 없으니 시간이 많이 들더라도 코드를 잘 이해하고 넘어가는 것을 추천드립니다.

 

만약 C++11을 사용할 수 없다면 크루스칼 알고리즘과 비슷하게 tuple<int,int,int> 대신 pair<int, pair<int,int> > 를 활용하면 됩니다.

 

PQ에 각 간선은 최대 1번씩 들어가고 또 최대 1번씩 삭제됨을 알 수 있습니다. 삽입, 삭제 각각의 시간복잡도는 $O(lgE)$이므로 프림 알고리즘의 시간복잡도는 $O(ElgE)$가 됩니다.

 

BOJ 1197번: 최소 스패닝 트리를 프림 알고리즘으로 해결한 코드를 확인해보세요.

 

이번 강의를 통해 최소 신장 트리에 대한 모든 것을 알게 되었습니다. 크루스칼 알고리즘은 구현이 쉬운 편이지만 Union-Find을 알아야하고, 프림 알고리즘은 다른 선수 지식이 필요없지만 힙을 비롯한 여러 STL들을 자유자재로 쓸 수 없으면 구현에서 상당히 애를 먹게되고.. 여러모로 힘든 차시네요. 이 강의를 들으시는 여러분들은 일단 두 알고리즘 모두 방법은 알아두고 각자의 상황에 맞춰 하나를 언제든지 짤 수 있게끔 준비해두시면 되겠습니다. 만만하지 않으니 조급하게 생각하지 마시고 조금씩 익히세요.

 

그룹에 연습 문제들을 올려두었는데, 사실 이미 최소 신장 트리와 관계있는 문제라는 것을 알고 풀기 때문에 조금 아쉽습니다. 코딩테스트에서 최소 신장 트리 관련 문제가 나온다면 구현도 문제지만 "이 문제에서 요구하는 것이 최소 신장 트리이구나"를 잘 캐치하는 것이 더 중요하다고 할 수 있겠습니다.