최소신장트리 도입

1. 최소신장트리란?

트리는 그래프의 노드들과 모든 노드간의 관계를 나타내는 간선들로 이루어진다.

최소신장트리란, 당연하게도 신장트리들 중에 가장 작은 규모의 트리를 말한다.

신장트리란 주어진 그래프의 모든 노드를 포함하면서, 모든 노드간에 관계가 있는(경로가 있는) 트리를 말한다.

다만 사이클은 포함하지 않아야 한다. 

규모라는 의미는, 간선들의 크기와 수에 비례하는 척도다.

따라서 최소신장트리는 신장트리를 만드는 여러 경우들 가운데 간선들의 크기(비용)의 합이 가장 작은 경우를 말한다.(사이클 미포함)

2. 최소신장트리를 구하는 알고리즘

그렇다면 최소신장트리를 어떻게 구할 수 있을까?

먼저 대표적인 알고리즘으로 크루스칼 알고리즘이 있다.

크루스칼 알고리즘의 흐름은 다음과 같다.

1) 간선들을 비용이 작은 순으로 정렬한다.

2) 가장 작은 간선부터 신장트리로 포함시킨다.(단 포함시키면 사이클이 생겨버리는 간선은 포함시키지 않는다.)

3) 모든 정점이 연결되지 않았다면 2단계로 돌아간다.

3단계로 보아 모든 정점이 포함될 것은 자명하고, 2단계의 제약조건으로 보아 사이클은 생기지 않을 것이다.

따라서 결과물이 신장트리가 될 것은 분명하다. 하지만 그 신장트리는 가장 작은 신장트리인가?

크루스칼 알고리즘이 최소신장트리를 찾는다는 증명은 다음과 같다.

우리는 다음을 귀납적으로 증명할 것이다 :

"알고리즘의 2단계를 수행하고 난 뒤 골라진 간선들의 집합을 F라고 하면, 항상 F를 포함하는 최소신장트리가 있다"

1단계에선 F는 빈 집합이다. 당연히 F를 포함하는 신장트리가 있다.

2단계는 반복적으로 수행된다. 다음에 2단계가 수행되면서 간선 e가 포함된다.

(F+e) 이 집합을 포함하는 최소신장트리가 있음을 보여야 한다.

e는 정답인 최소신장트리의 간선일 수도, 아닐 수도 있다. 맞다면 잘한 것이나, 아닐 경우 문제가 있다.

e가 노드 a, b를 잇는 간선이라고 해보자. 또한 원래 정답인 최소신장트리 또한 a에서 b로가는 경로를 유일하게 갖고 있다.

헌데 e를 추가함으로써 (F+e)는 사이클을 갖게된다. 이는 규칙에 어긋나므로 e가 정답의 일부임을 증명하였다.

두 번째 알고리즘으로 프림 알고리즘이 있다.

크루스칼 알고리즘이 최소신장트리를 이곳 저곳 따로 완성시켜나가는 반면, 프림은 한 지점부터 확장시켜나가면서 완성시킨다.

1) 아무 노드나 시작점으로 정한다.(A)

2) 그 노드에 연결된 간선 중 비용이 가장 작은 간선(A-B)을 포함시킨다. 단 B는 지금까지 연결되지 않은 노드이다.

3) A, B 아무 노드나 정하고 2를 반복한다.

최소신장트리를 완성해 나가는 과정은 선형시간에 가능하다.(크루스칼의 사이클을 확인하는 과정은 디스조인트-셋으로 간소화된다)

시간을 잡아먹는 작업은 가장 비용이 작은 간선을 찾는 작업에서 비롯된다.

크루스칼은 처음에 모든 간선을 정렬해야 하고, 프림은 각 단계의 노드와 연결된 간선들을 정렬해야한다.

따라서 시간 복잡도는 다음과 같다. 

3. 최소신장트리를 구해야 하는 문제들

1) 1197 최소 스패닝 트리 : https://www.acmicpc.net/problem/1197

말 그대로인 문제.

풀이 : http://js1jj2sk3.tistory.com/23

2) 1922 네트워크 연결 : https://www.acmicpc.net/problem/1922

모든 노드를 연결하는 최소비용을 구해야 한다. 최소신장트리의 정의를 알고 있는지 묻고 있다.

풀이 : http://js1jj2sk3.tistory.com/24

3) 1647 도시 분할 계획 : https://www.acmicpc.net/problem/1647

그래프를 두 최소신장트리로 나누려고 한다. 최소신장트리의 간선 수는 (노드의 수(n) - 1)임을 생각해보자.

풀이 : http://js1jj2sk3.tistory.com/25

4) 9372 상근이의 여행 : https://www.acmicpc.net/problem/9372

가장 적은 종류의 비행기를 탄다 = 가장 간선의 수가 적은 트리는 ? = 최소신장트리

풀이 : http://js1jj2sk3.tistory.com/26

5) 2887 행성 터널 : https://www.acmicpc.net/problem/2887

최소신장트리를 구해야 하는 문제임은 명확하지만, 간선이 모호하게 주어졌다. 

풀이 : http://js1jj2sk3.tistory.com/27

6) 1944 복제 로봇 : https://www.acmicpc.net/problem/1944

어느 지점을 노드화 시키고, 간선의 비용은 어떻게 구할 것인지가 중요하다.

풀이 : http://js1jj2sk3.tistory.com/28