[실전 알고리즘] 0x1B강 - 최소 신장 트리

 

 

안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Spanning이나 신장 이 단어가 너무 낯설지 않나요? 뭐 저만 그런거라면 할 말은 없습니다.

 

최소 신장 트리를 구하는 대표적인 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있는데 각각이 무엇인지를 알아보고 연습 문제를 같이 풀어보겠습니다.

 

최소 신장 트리를 다루기 전에 신장 트리가 무엇인지 알아봅시다. 신장 트리는 주어진 방향성이 없는 그래프의 부분 그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리를 의미합니다. 부분 그래프는 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프를 의미합니다.

 

신장 트리의 정의를 그냥 읽었을 때에는 무슨 소리인가 싶을 수도 있는데 그림을 보면 명확하게 이해할 수 있습니다. 왼쪽과 같은 그래프가 있을 때, 오른쪽에 있는 그래프들은 전부 왼쪽 그래프의 신장 트리입니다. 일단 모든 정점을 포함한 서브그래프이고, 트리이기 때문입니다(트리는 0x19강 - 트리 단원에서 배웠듯 무방향이면서 사이클이 없는 연결 그래프입니다). 트리의 성질로부터 주어진 그래프의 정점이 V개일 때 신장 트리는 V-1개의 간선을 가지고 있음을 알 수 있습니다. 그리고 상식적으로 생각했을 때 주어진 그래프가 연결 그래프일 때만 신장 트리가 존재합니다.

 

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

 

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

 

이제 최소 신장 트리를 구하는 첫 번째 방법인 크루스칼(Kruskal) 알고리즘을 알아보겠습니다. 미리 안타까운 소식을 알려드리자면 크루스칼 알고리즘은 Union Find라는 알고리즘을 모르면 효율적으로 구현할 수 없습니다. 그리고 Union Find 알고리즘이 엄청 난이도가 있는 것은 아니지만 그렇다고 설명을 처음부터 하자고 하니 분량이 좀 많기도 하고, 단순히 구현을 하는 것 말고도 관련해서 할 얘기가 좀 있는데 여기서 설명을 해버리면 그런 얘기들을 다 할 수가 없기 때문에 Union Find는 여기서 소개를 드리지 않고 따로 부록으로 빼두었습니다. 정리하면 지금 크루스칼 알고리즘이 무엇인지는 알려드리지만 실제 구현 코드는 Union Find를 모를 경우 완성을 할 수 없습니다.

크루스칼 알고리즘은 Union Find 알고리즘을 알고 있다고 가정할 때 뒤에 나올 프림 알고리즘보다 구현이 쉬운 알고리즘입니다. 그래프 관련 단원을 한데 모으다보니까 Union Find 알고리즘이 부록으로 빠지게 되었는데 시간이 넉넉하시면 아예 Union Find를 지금 익히고 내용을 이어가셔도 됩니다. 만약 그냥 Union Find 알고리즘은 나중에 익힐 생각이라고 한다면 비록 Union Find를 몰라서 구현 코드는 작성을 못한다고 해도 크루스칼 알고리즘이 무엇인지는 알고 있는게 좋다고 생각하기에 가능하면 크루스칼 알고리즘을 익혀가시면 좋겠지만 시간이 없고 단지 최소 신장 트리의 구현법만이 궁금한 경우에는 크루스칼 알고리즘을 뛰어넘고 프림 알고리즘으로 바로 가셔도 됩니다. 프림 알고리즘은 지금까지 배운 지식만을 이용해서 구현이 가능합니다.

크루스칼 알고리즘은 쉽게 요약을 하면 가장 비용이 낮은 간선부터 시작해 간선을 크기 순으로 살펴보며 서로 떨어져 있던 정점들을 합쳐나가서 총 V-1개의 간선을 택하는 알고리즘입니다. 글로 적어둔 과정을 확인해보세요. 이 설명에서 "같은 그룹으로 만든다"라는 표현이 낯설 수 있을 것 같습니다. 걱정하지 말고 실제로 그래프에서 크루스칼 알고리즘을 실행하는 과정을 확인해봅시다.

 

알고리즘을 시작해봅시다. 각 정점에 색이 칠해져있는데 이 색이 바로 그룹을 나타냅니다. 맨 처음에는 모든 정점이 서로 다른 그룹에 속해 있는 상태로 시작합니다.

 

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

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

 

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

 

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

 

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

 

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

 

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

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

결론적으로 말해서 이 알고리즘의 정당성, 즉 이 알고리즘이 반드시 최소 신장 트리를 반환하는 사실은 귀납법을 이용해서 증명하거나 매트로이드라는 수학적 개념을 빌려와 조금 더 쉽게 설명할 수 있습니다. 그러나 증명이 좀 많이 복잡해서 그래프 이론을 심도 깊게 배우려고 하거나 아예 알고리즘을 전공하고자 하는게 아니면 굳이 알 필요는 없다고 생각합니다. 그렇기에 증명은 생략합니다.

 

그런데 "특정 두 정점이 같은 그룹인지 다른 그룹인지"를 어떻게 판단할 수 있을까요? 현재 우리가 배운 내용만을 가지고 판단하는 방법을 한 번 고민해봅시다. 이건 바로 Flood Fill을 이용해 해결할 수 있습니다. 최소 신장 트리에 편입시킨 간선을 별도로 관리하고 있다고 할 때 정점 A와 B가 같은 그룹인지 판단하려면 최소 신장 트리에 편입시킨 간선들만을 가지고 A에서 B로 갈 수 있는지, 즉 A에서 Flood Fill을 돌렸을 때 B를 방문하는지 확인하면 됩니다. 그런데 이 과정에서 필요한 시간복잡도는 O(V)입니다. 정확히는 O(V+E)인데 트리의 특성상 매번 간선의 수 E가 V-1 이하이기 때문에 결론적으로 O(V)가 됩니다. 그렇기 때문에 Flood Fill을 이용해 크루스칼 알고리즘을 구현할 경우 간선의 정렬에서 O(ElgE), 이후 최대 E번에 걸쳐 같은 그룹인지 판단하는 과정이 필요하므로 O(VE)가 필요해 최종 시간복잡도는 O(ElgE + VE)가 되어 많이 비효율적입니다.

Flood Fill을 사용하면 비효율적이지만 Flood Fill 대신 Union Find를 사용할 경우 "특정 두 정점이 같은 그룹인지 다른 그룹인지"를 사실상 상수 시간에 확인할 수 있습니다. 정확히는 아커만 역함수라는 생전 처음 들어봤을 함수의 값이 계수로 붙긴 하지만 이 함수의 값은 현실적인 범위 안에서 항상 4 이하이기 때문에 상수 시간이라고 생각하셔도 무방합니다. Union Find를 이용해서 크루스칼 알고리즘을 구현하면 O(ElgE + VE) 대신 O(ElgE)로 해결이 가능합니다. 코드를 직접 짜보시면 좋겠지만 조금 어려울 것 같아 바로 제 코드를 보면서 설명을 드리도록 하겠습니다.

 

앞에서 언급한 것 처럼 Union Find는 이번 강의에서 다룰 내용이 아니니 "특정 두 정점이 같은 그룹인지 다른 그룹인지"는 is_diff_group 이라는 함수에서 처리해준다고 생각을 하고 코드를 보겠습니다. 이 함수는 Flood Fill로도, Union Find로도 구현할 수 있지만 Union Find로 구현해야 더 효율적인 시간복잡도로 최소 신장 트리를 구할 수 있습니다. 이전 강의들에서는 간선을 vector<int> adj[10]에 저장했는데 크루스칼 알고리즘에서는 간선을 크기 순으로 정렬하는 과정이 필요하기 때문에 인접 리스트 형식을 사용하는 대신 전부 tuple<int,int,int> edge 배열에 저장해둡니다. tuple의 대소 비교는 제일 앞의 값부터 비교해서 이루어지므로 비용, 정점 1, 정점 2 순으로 담아둡니다.  

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

어차피 프림 알고리즘을 익히고 나면 지금까지 강의에서 다룬 내용만으로도 O(ElgE)에 최소 신장 트리를 구할 수 있기 때문에 O(ElgE + VE) 시간복잡도의 알고리즘은 필요가 없습니다. 그래서 다음 슬라이드에서는 Union Find를 사용한 크루스칼 알고리즘을 알려드릴테니 Union Find를 알고 계시거나 따로 공부할 의향이 있으시면 확인해보시고, 그렇지 않을 경우 지금은 넘어갔다가 Union Find를 배운 후 다시 확인하시면 됩니다.

 

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

 

main 함수를 먼저 살펴보시면 앞에서 소개한 코드와 흐름이 동일합니다. 이 문제에서는 단순히 간선의 합만 계산하면 되기 때문에 is_diff_group 반환 값이 true인 간선을 찾아낸 후에는 다른 처리 없이 ans에 cost를 더했습니다. 이해를 돕기 위해 is_diff_group 이라는 함수명으로 써놓았지만 Union Find를 이전에 공부했다면 해당 과정이 Union Find 알고리즘의 Union임을 알 수 있습니다. Union by rank를 하기 위해 Union 부분의 코드가 다소 난잡해졌는데, 꼭 Union by rank를 하지 않고 그저 경로 압축만 진행하더라도 로그 스케일로 떨어져서 문제를 통과하는데 큰 무리가 없습니다. (코드)

 

다음으로 최소 신장 트리를 구하는 두 번째 방법인 프림(Prim) 알고리즘을 알아봅시다. 프림 알고리즘은 Union Find가 필요했던 크루스칼 알고리즘과 다르게 우선순위 큐를 가지고 구현을 할 수가 있습니다. 그렇지만 크루스칼 알고리즘에 비해 구현이 조금 어려운 편입니다.

크루스칼 알고리즘이 가장 비용이 낮은 간선부터 시작해 서로 떨어져 있던 정점들을 합쳐나가며 총 V−1개의 간선을 택하는 알고리즘이었다면, 프림 알고리즘은 한 정점에서 시작해 확장해나가는 알고리즘입니다. 글로 읽었을 때 충분히 이해가 갈 것 같은데 설령 조금 헷갈리더라도 뒤에서 과정을 직접 살펴보면 쉽게 방법을 터득할 수 있습니다.

프림 알고리즘 또한 매 순간마다 가장 비용이 낮은 간선을 택하는 그리디 알고리즘이고 해당 알고리즘이 왜 최소 신장 트리를 반환하는지를 증명할 필요가 있습니다. 증명의 흐름은 크루스칼 알고리즘의 정당성 증명과 비슷하고, 크루스칼 알고리즘에서 증명을 하지 않은 이유와 똑같은 이유로 증명은 건너뛰도록 하겠습니다. 이제 같이 프림 알고리즘의 과정을 살펴봅시다.

 

알고리즘을 시작해봅시다. 우선 하나의 정점을 잡아 최소 신장 트리에 추가해야 합니다. 아무거나 잡아도 상관이 없지만 임의로 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개의 간선을 최소 신장 트리에 추가시켰습니다. 그러므로 최소 신장 트리를 만들어내는데 성공했고 알고리즘은 종료됩니다. 과정을 잘 따라오셨다면 프림 알고리즘은 임의의 한 정점에서 시작해 매번 가장 낮은 비용의 간선을 찾아 점점 뻗어나가는 모양임을 알 수 있습니다.

방법 자체는 크게 어렵지 않게 이해하실 수 있을 것 같은데, 진짜 문제는 프림 알고리즘의 구현입니다. 과연 이 알고리즘을 어떻게 구현해야 할까요? 우리가 대충 지금 손으로 했던 방법을 그대로 구현하려고 한다면 V−1번에 걸쳐 현재 최소 간선 트리에 포함된 정점과 그렇지 않은 정점을 연결하는 모든 간선을 조사하고 이들 중에서 최소 비용인 간선을 택하는 방식으로 구현할 수 있습니다. 하지만 이렇게 구현을 하면 O(VE)가 되어서 많이 비효율적입니다.

 

프림 알고리즘의 과정을 보면 매번 비용이 최소인 간선을 택해야 하고 또 선택할 수 있는 간선이 추가되기도 하니 이 상황을 놓고 봤을 때 생각나는 자료 구조가 하나 있어야 합니다. 프림 알고리즘을 효율적으로 구현하기 위해서는 우선순위 큐가 필요합니다. 우선순위 큐가 기억이 나지 않는다고 하시면 조금 마음이 아픕니다. 만약 기억이 나지 않는다면 0x17강을 다시 보고 오세요.

우선순위 큐에 간선들을 적절히 넣어두면 매 순간마다 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중에서 최소를 효율적으로 알아낼 수 있습니다. 실제 구현에 초점을 맞춘 프림 알고리즘을 다시 소개하겠습니다. 과정을 확인해보시고 실제 예시를 보여드리겠습니다.

 

알고리즘을 시작해봅시다. 우선 하나의 정점을 잡아 최소 신장 트리에 추가해야 합니다. 아무거나 잡아도 상관이 없지만 임의로 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과 1, 3과 4, 3과 5를 연결하는 간선으로 총 3개가 있습니다. 1, 4, 5번 정점 중에서 1번 정점은 최소 신장 트리에 이미 포함된 정점이므로 3과 4, 3과 5를 연결하는 간선만 우선순위 큐에 추가합니다.

 

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

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

 

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

 

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

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

 

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

 

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

 

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

 

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

 

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

 

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

맨 처음 대략적인 설명을 들을 땐 쉬웠는데 우선순위 큐가 들어간 실제 구현 파트가 까다롭게 느껴질 것 같습니다. 다소 난해하지만 이 알고리즘의 흐름이 2강 후에 다루게 될 다익스트라 알고리즘과 매우 유사하기 때문에 지금 이해를 잘 하고 넘어가면 다익스트라 알고리즘을 이해할 때 편합니다. 구현이 많이 어렵겠지만 그래도 도전 정신을 가지고 구현을 직접 시도해봅시다. 다음 슬라이드에는 바로 구현 코드가 나옵니다.

 

코드로 구현하면 위와 같습니다. 일단 adj는 BFS에서 하던 것과 달리 간선의 비용과 정점 번호 이 2개를 pair로 들고 있습니다. 나중에 보시면 알겠지만 간선의 비용 정보가 필요해서 이렇게 두었습니다. chk[i]는 i번째 정점이 최소 신장 트리에 포함되었는지 여부를 저장하는 변수입니다.

 

또 코드에서 priority_queue의 선언이 굉장히 보기 싫게 생겼지만 어쩔 수 없습니다. 그냥 priority_queue<tuple<int,int,int>> 으로 쓰면 최대 힙인데 최소 신장 트리에서는 최소 힙이 필요하므로 11-13번 줄과 같이 선언했습니다. 17번째 줄과 27번째 줄과 같이 우선순위 큐에 값을 넣을 때에는 현재 최소 신장 트리에 속하지 않은 정점의 번호를 제일 마지막에 가도록 했기 때문에 chk[a]은 반드시 true입니다. 그러므로 현재 보고 있는 간선이 최소 신장 트리에 포함된 두 정점을 연결한 간선인지 최소 신장 트리에 포함된 정점과 포함되지 않은 정점을 연결한 간선인지 판단하기 위해서는 21번 줄과 같이 chk[b]만 확인하면 됩니다.

무엇보다도 STL이 친숙하지 않다면 코드를 이해하기가 어려울 수 있습니다. 그래도 한 줄씩 뜯어서 보면 코드의 흐름 자체는 앞서 살펴본 과정을 거의 그대로 옮긴 상황이라 시간이 많이 들더라도 코드를 잘 이해하고 넘어가는 것을 추천드립니다.

프림 알고리즘의 시간복잡도를 생각해보면 각 간선은 우선순위 큐에 최대 1번씩 들어가고 또 최대 1번씩 삭제됩니다. 우선순위 큐에서 삽입, 삭제 각각의 시간복잡도는 O(lgE)이므로 프림 알고리즘의 시간복잡도는 O(ElgE)입니다.

 

BOJ 1197번: 최소 스패닝 트리 문제를 프림 알고리즘으로 해결한 코드를 확인해봅시다. 참고로 이 문제처럼 실제 최소 신장 트리의 간선 목록을 요구하는 대신 가중치의 합만을 요구할 경우에는 우선순위 큐에 {비용, 정점 1, 정점 2} 형태로 원소를 저장할 필요가 없고 {비용, 정점 2}만을 저장해도 답을 구할 수 있습니다. 사실 저는 Union Find를 안다는 가정 하에 크루스칼 알고리즘의 구현이 더 쉽기 때문에 최소 신장 트리 관련 문제에서 크루스칼 알고리즘만을 사용하지만 혹시 프림 알고리즘을 자주 사용할 예정이라고 하면 가중치의 합만 필요할 경우에는 {비용, 정점 2}만 담은 pair<int, int>로도 해결이 가능하다는 사실을 알아가셔도 좋습니다. (코드)

 

마지막으로 같이 살펴볼 연습 문제는 BOJ 1368번: 물대기 문제입니다. 문제에서 물을 대고 있는 다른 논으로부터 물을 끌어오는 상황을 간선의 연결로 생각하면 뭔가 최소 신장 트리와 비슷한 느낌이지만 직접 논에 우물을 파는 것도 가능하기 때문에 조금 애매합니다. 프림 알고리즘이나 크루스칼 알고리즘이랑 비슷한 형태의 그리디한 풀이를 어찌저찌 만들 수는 있을 것 같은데 그 풀이의 정당성을 잡아내기도 쉽지 않습니다. 이럴 때에는 어떻게 해야할까요?

 

사실 지금 최소 신장 트리 이 단원에서 다루고 있어서 이 문제의 풀이가 최소 신장 트리임을 대놓고 알려주고 있기 때문에 약간 아쉽지만, 아무튼 여러분이 문제를 마주하고 열심히 고민한 끝에 최소 신장 트리와 비슷한 느낌으로 해결이 가능할 것 같다는 생각을 했다고 해보겠습니다. 이런 상황에서는 주어진 문제를 최소 신장 트리를 구하는 문제로 대응시킬 방법이 있는지 고민해볼 수 있습니다. 주어진 문제를 최소 신장 트리를 구하는 문제로 바꾸려면 그래프를 어떻게 변형시켜야 할지 적절한 그래프 모델링을 알아내야 하는데 이 부분이 상당히 어렵습니다. 그래도 사실 이렇게 그래프 모델링을 해서 문제를 풀어본 경험이 있으신 분이 여럿 계실 것 같습니다. 대표적으로 BFS 단원의 문제집에 있던 BOJ 1600번: 말이 되고픈 원숭이 문제, BOJ 14442번: 벽 부수고 이동하기 2 문제 등의 풀이를 다시 떠올려보면 이 문제들은 이전의 BFS 문제들처럼 상태 공간을 (x, y) 꼴의 2차원에서 잡는 방식으로는 해결이 안되니 벽을 부순 횟수나 말의 움직임을 사용한 횟수 등을 추가로 상태 공간에 편입시켜 거기서 BFS를 돌리는 방식이었고 다르게 말하면 주어진 2차원 그래프로부터 새로운 3차원 그래프를 모델링한 후 거기에서 BFS를 했다고 생각할 수도 있습니다.

 

이렇게 특정 그래프 알고리즘이 적용될 수 있을 것 같지만 상황이 100% 맞아떨어지지는 않을 때 적절하게 그래프 모델링을 하는 아이디어는 비단 BFS나 최소 신장 트리 문제가 아니더라도 다익스트라, SCC, 최대 유량 문제 등에서 자주 등장하는 풀이 기법입니다. 다만 이러한 그래프 모델링 유형의 문제는 굉장히 난이도가 높은 편입니다. 그래서 어떻게 보면 코딩테스트 용으로는 과할 수도 있긴 한데 최소 신장 트리가 이런 방식으로도 응용이 가능하다는걸 보여드리고 싶어서 강의에 추가했어요. 상당히 어려운 문제이니 감이 오지 않는다고 자책할 필요는 전혀 없습니다.

 

서론이 굉장히 길었는데 이제 문제로 다시 돌아와보겠습니다. 주어진 예제를 그림으로 나타내보았습니다. 사실 그래프 모델링이라는게 보고 나면 바로 무릎을 탁 치면서 풀이를 잡아낼 수 있는데 모르면 전혀 감이 안오는 그런 유형이라 한 번 먼저 시도를 해보라고 하기도 미안한 느낌이 있습니다. 그래도 한 번 이 문제의 상황을 최소 신장 트리로 바꿀 방법을 고민해봅시다. 힌트를 드리자면 가상의 무언가를 하나 두면 됩니다. 다음 슬라이드에 바로 방법이 나옵니다.

 

그 방법은 바로 가상의 정점을 하나 둬서 우물을 파는 비용을 그 정점까지의 비용으로 두는 방법입니다. 굉장히 신박하지 않나요? 제 강의의 독자라면 이 풀이를 보고 감탄해서 기립박수를 쳐야한다고 생각합니다. 원래 문제에서 모든 논에 물을 대는 방법은 지금 이 그래프에서의 신장 트리로 대응됩니다. 그렇기 때문에 여기서 최소 신장 트리를 구하면 자연스럽게 문제를 해결할 수 있습니다. 이 문제를 통해 주어진 그래프를 가상의 정점 혹은 간선을 둔 새로운 그래프로 변경하는 테크닉을 습득할 수 있습니다.

 

이 문제는 그래프 모델링이 핵심이고 최소 신장 트리를 구하는 과정은 앞에서 본 내용의 반복이라 딱히 설명이 필요하지 않아보입니다. 저는 크루스칼 알고리즘을 이용해 구현했지만 당연히 프림 알고리즘을 이용해도 아무 상관 없습니다. (코드)

 

이번 강의에서는 최소 신장 트리를 익혔습니다. 크루스칼 알고리즘은 구현이 쉬운 편이지만 Union Find을 알아야 하고, 프림 알고리즘은 다른 선수 지식이 필요없지만 우선순위 큐를 비롯한 여러 STL들을 자유자재로 쓸 수 없으면 구현에서 조금 애를 먹게 됩니다. 일단 두 알고리즘 모두 방법은 알아두고 각자의 상황에 맞춰 어느 하나를 언제든지 짤 수 있게끔 준비해두시면 되겠습니다.

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