백준에서 골드 문제를 랜덤으로 돌리던 중 1414번 불우이웃돕기를 만나게 되었다. 한 30 ~ 40분 정도를 고민해서 풀이의 방향은 잡았었는데, 내 생각에 자신이 없어서 결국 풀이를 검색했다. MST(Minimum Spanning Tree) 라는 부류의 문제였고 MST 를 푸는 대표적인 알고리즘 중 하나인 크루스칼 알고리즘이 내 초기 아이디어와 거의 동일한 방법이었다는 것을 알게 되었다. '그냥 내 풀이대로 밀고나가볼걸' 이라는 아쉬움을 느끼긴 했지만, 확신할 수 없는(다시 말해 증명할 수 없는) 직관은 허무할 수 밖에 없다라는 결론에 도달하게 되었다.
크루스칼 알고리즘은 사실 간단하다. 그리디라는 기본 자세를 가지고 가지를 뻗어나가면 되는 것이다. 나 정도의 사람도 직관적으로 떠올릴 수 있는 방법이다. 그러나 내가 내 생각에 자신이 없던 것처럼 직관이 확신으로 이어지지는 않는다. 그러기 위해선 증명이 필요하다. 인터넷에 크루스칼을 증명하는 글은 많지만 대부분의 글은 직관에 다가가기 보다는 많은 수식들로 나같은 사람(학술적 목적이 아닌 간편한 이해를 원하는)을 당황하게 만든다.
그래서 내가 이해한 크루스칼 알고리즘의 증명을 최대한 직관적으로 남겨 놓으려고 한다.
내가 참고한 글 - [https://gazelle-and-cs.tistory.com/103] (수식 많음 주의)
CASE 1.
증명이라는 것은 보통 Bottom - UP 방식으로 쌓아가기 마련이지만, 나는 Top - Down 방식으로 가장 직관적인 상황을 제시한다.
6개의 정점이 주어진 상황이다. A 정점이 있고, A 정점을 제외한 정점의 집합을 B 집합이 있다. 이때 B 집합은 MST 의 간선에 의해 모든 정점이 이어져 있다. 이때 A 정점에는 3개의 간선이 있고 각각 가중치가 2, 5, 7 이라고 한다. 이때 MST 는 세개의 간선 중 어떤 간선을 가지고 있을까? 우선 생각해야하는 것은 N개의 정점이 있을 때, 간선은 N-1 개가 선택 되어야 MST 의 조건을 만족한다는 것이다 때문에 3개중 1개의 간선만 택하면 MST 가 완성된다. 당연하게도 최소의 가중치를 가지는 2번 간선(앞으로 n 가중치를 가지는 간선을 n번 간선 이라 부르겠다.)을 골라야 할 것이다.
그런데 약간 절차를 달리해서, 아래와 같이 생각하는 것이 앞으로의 과정을 이해하는 데 도움이 된다.
1) 우선 7번 간선을 골라 Spanning Tree 를 완성한다.
2) 여기에 5번 간선을 추가하면 Tree 구조가 깨지고 순환이 생긴다. (3개의 정점을 포함하는)
3) 5번 간선을 유지하고 7번 간선을 버린다.
(순환이 생기는 구간에서는 간선 중 어떤 것을 제외해도 여전히 정점간의 연결이 유지된다.)
4) 여기에 2번 간선을 추가하면 Tree 구조가 깨지고 순환이 생긴다. (6개 정점을 포함하는)
5) 2번 간선을 유지하고 5번 간선을 버린다.
6) 2번 간선이 남는다.
이런식의 절차를 따르면, 2의 간선이 최후에 선택이 될 것이다.
이로부터 한가지 더 알아야 할 점이 있다. MST 에 간선을 하나 추가하면 필연적으로 순환이 생긴다는 것이다. 이 점을 염두에 두고 다음으로 넘어가자
CASE 2.
다음 상황이다. CASE 1 과는 다른 독립적인 상황이다.
자 그림을 보면 B 집합은 MST 의 간선에 의해 모두 연결이 되어있다. 자 이때 남아있는 간선 중 MST 가 어떤 간선을 가지게 될까?
이번에도 아래와 같은 절차대로 생각해보자.
1) 우선 3, 5번 간선을 고른다.
2) 여기에 2 번 간선을 추가하면 순환이 생긴다.
3) 가중치가 큰 5번 간선을 버리고, 2번 간선을 고른다.
4) 여기에 1번 간선을 추가하면 다시 순환이 생긴다
5) 가장 가중치가 큰 3번 간선을 버리고 1번 간선을 고른다.
6) 1, 2 번 간선만 남는다.
여기서 알 수 있는 점은 2, 3, 5 가중치 중 어떤 가중치를 고르더라도 간선 하나를 추가하면 순환이 생기고, 이와 순환을 이루는 간선중 큰 간선은 버려진다. 는 것이다. 따라서, 가중치가 작은 1번 간선은 MST 에 포함되게 된다.
CASE 3.
같은 방식으로 아래의 상황도 같은 방식으로 고민해보자.
이번에는 MST 간선이 세개로 나누어져 있다. 가장 먼저 어떤것을 포함된다고 생각할 수 있을까? 당연히 1번 간선을 생각할 수 있다. 왜냐하면 다른 간선을 고르더라도 결국 1번을 통해 순환이 만들어 질 수 있고, 그 과정을 통해 다른 간선을 밀어내버리면 되기 때문이다.
여기서 또 다시 염두에 두어야 할 것이 생긴다. 1번 간선을 고르게 되면, 이후에는 7번 간선은 아예 선택의 대상에서 제외 된다는 것이다. 왜냐하면 1번 간선을 포함시킨 뒤 7번 간선을 포함시키게 되면 Tree 구조가 깨어지며 순환이 생기게 되고, 7번 간선은 이전에 선택된 1번 간선보다 절대적으로 클 것이기 때문이다.(1번 간선이 선택된 이유는 그것이 가장 최소값이었기 때문이다.) 따라서 간선을 선택할 때에는 순환 고리가 생기는 간선은 자동적으로 선택의 과정에서 제외된다.
CASE 4.
여기서는 어떤 간선을 고르면 될까? 자신있게 8번 간선을 먼저 고르면 될 것 같지만, 8번 간선을 고르는 것이 반드시 나은 선택지라는 것에 대해 직관적으로 안심이 들지 않기 때문에 조금 당황스럽다. 하지만 8을 고르지 않고 스패닝 트리를 완성시키는 경우를 조금만 생각해 보면, 모든 경우에 대해 8로 순환 고리를 만들 수 있으며, 8보다 큰 간선은 8에 의해 버려지게 될 것임을 알 수 있다.
결론.
위 과정을 일축해보자면 이렇다. 특정 스패닝 트리에서, 스패닝 트리를 이루는 간선보다, 더 작은 가중치가 있는 간선이 있다면, 순환 고리를 통해 다른 간선을 밀어낼 수 있다. 때문에 가장 가중치가 가장 작은 간선을 고르면서 뻗어나가는, 그리디한 방식으로 간선을 택하면 최소 가중치가 보장된다.
