[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 42회차 미션

1. 최소 신장 트리 ( Minimum Spanning Tree )

최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다.

이전 글에서 살펴봤던 BFS, DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다.

MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다.

 

이해를 돕기 위해 예제를 살펴보도록 하겠습니다.

 

2. 주요 용어

MST에서 핵심이 되는 용어는 안전간선(Safe edge)입니다.

안전간선을 정의하기 위해서는 4가지의 용어가 필요하므로, 이 용어들을 살펴보고 안전간선을 정의하도록 하겠습니다.

 

 

1) 단절

단절은 트리의 모든 정점들의 집합을 V라고 할 때, 어떤 정점들의 집합 S가 있어서 두 개의 집합 ( S , V - S )로 나누는 것을 말합니다.

단순히 모든 정점들을 두 집합으로 분리했다고 생각하면 됩니다.

 

 

2) 교차한다

단절된 두 집합( S , V-S )에 대해, 간선( u , v )의 한 종점이 S, 다른 종점이 V-S에 속한다면 간선( u , v )는 단절( S , V - S )와 교차한다고 합니다.

 

 

3) 따른다

MST의 부분집합 A에 대해 단절을 건너는 간선이 없다면 단절이 집합 A를 따른다고 합니다.

 

 

여기서 파란색 간선들은 MST의 결과가 될 트리의 부분집합입니다.

즉, A는 파란색 간선들을 모두 갖는 집합이라고 할 수 있습니다.

 

단절이 A를 따른다는 것은 A의 간선 중 단절과 교차하는 것이 없다는 것을 의미합니다.

따라서 1번 그림은 단절이 A를 따르지만, 2번 그림은 단절이 A를 따르지 않습니다.

 

 

 

4) 경량간선

단절과 교차하는 간선 중 가중치가 최소인 간선을 경량간선이라고 합니다.

 

 

 

5) 안전간선

연결된 무방향 그래프 G=( V , E )에 대해서 A를 MST의 부분집합이라 하고,

( S , V - S )가 A를 따르는 어떤 단절이라 하며, ( u , v )를 단절과 교차하는 경량간선이라 할 때 ( u , v )는 A의 안전간선이라고 합니다.

 

안전간선은 위에서 언급한 용어들이 전부 언급되어 정의됩니다.

이해가 안되시면 정의의 용어들을 하나하나 생각해보시면 이해가 될 것입니다.

 

안전간선이 중요한 이유는 MST가 안전 간선들을 연결하여 트리를 생성하기 때문입니다.

즉, MST는 안전간선을 연결하여 트리를 생성하는 것이 규칙입니다.

1. Dijkstra's 알고리즘 vs Prim's 알고리즘

SSP의 두 번째 알고리즘 Dijkstra's 알고리즘에 대해 알아보겠습니다.

Dijkstra's 알고리즘은 이전에 MST의 Prim's 알고리즘과 매우 흡사합니다.

( Prim's 알고리즘은 여기를 참고해주세요 ! )

Dijkstra's 알고리즘도 최소 우선순위 큐를 이용해서 하나의 정점으로부터 인접한 간선들을 확장해 나가는 방식입니다.

 

Prim's 알고리즘은 MST를 만들기 위해서 가중치와 정점의 key 값을 비교하여 key 값을 업데이트 할지 말지를 결정했습니다.

SSP에서는 이를 Relax라고 표현을 했습니다.

Relax는 key값이 없고, 최단 경로 추정 값(d[v])을 이용하여 d[v]를 업데이트 할지 말지를 결정했습니다.

그리고 Relax는 정점의 key값이 딱 주어진 것이 아니라 최단 경로 추정 값들이 누적되어온 결과입니다.

이런 점에서 Prim's 알고리즘과 Dijkstra's 알고리즘은 다릅니다.

 

Dijkstra's 알고리즘의 동작하는 방식은 Prim's 알고리즘과 비슷하므로 바로 동작 과정을 살펴보도록 하겠습니다.

 

 

 

 

2. Dijkstra's 알고리즘

Dijkstra's 알고리즘은 먼저 모든 정점들을 최소 우선순위 큐에 삽입합니다.

그리고 최단 경로 가중치 값( d[v] )이 가장 작은 정점을 선택하여 인접 간선들에 대해 Relax를 수행하여, 시작 정점으로부터 각 정점까지의 최단 경로 비용을 계산합니다.

 

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG