BOJ 1626 두 번째로 작은 스패닝 트리

스패닝 트리(Spanning Tree)는 그래프에서 일부 간선을 선택해서 만든 트리이고, 최소 스패닝 트리(Minimum Spanning Tree, MST)는 스패닝 트리 중에 선택한 간선의 합이 최소인 트리이다.
이 문제에서 방향성이 없는 그래프G가 주어지고, 이 그래프G에는 MST가 존재하는데 MST의 간선의 합보다는 큰 스패닝 트리 중 최소인 스패닝 트리의 간선의 합을 구하는 문제이다. 즉 모든 스패닝 트리의 간선의 합 중 두 번째로 작은 값을 구하는 문제이다.

e== v-1 인 경우에는 즉, 그래프G 자체가 MST인 경우에는 두 번째로 작은 스패닝 트리는 존재하지 않을 것이므로 -1을 출력해야 할 것이다. 물론, 모든 정점이 edge로 연결되어 있을 때이야기 이다. 만약 모든 정점이 edge로 연결되어 있지 않고, 그냥 동떨어져 있다면 e==v-1이라도 성립하지 않을 수 있을 것이다. 그리고 이 뿐 아니라 spanning tree를 어떻게 만들어도 그것이 MST가 된다면(가중치가 같은 edge가 여러개 있다든지...) 또한 두 번째로 작은 스패닝 트리는 존재하지 않을 것이다.
그런데, MST가 존재하지 않는 경우도 있을까? 아 정점이 1개이고, edge가 1개인 경우면 사이클이 생기므로 (tree는 사이클이 없는 그래프이기도 하다) MST가 존재하지 않을 것이다.
 이 외에도 여러 경우가 있을 수 있지만 일단 생각해본 것만 적어봤다.

일단 생각해본 것이 MST를 Prim이나 Kruskal 알고리즘을 이용해서 구하고, MST를 구성하는 간선 중 가장 가중치가 큰 간선과 MST를 구성하지 않는 다른 간선과 바꾸는 것인데, 하지만 spanning tree가 되는 경우만 바꿀 수 있고, 가중치가 가장 큰 간선의 경우 바꾸면 안되는 경우도 있을 수 있고... 까다롭다. 근데 이 것을 생각하면서 kruskal알고리즘의 과정을 생각해봤는데, kruskal알고리즘을 통해 MST를 구하면서 두 번째로 작은 스패닝 트리를 구할 수도 있겠다라는 생각이 들었다. 최소힙(우선순위 큐)에 edge들을 넣어 놓고, 가장 작은edge부터 보면서 edge에 속한 정점이 서로 다른 집합이면 선택하는 것인데, 선택이 안 된 것들만 따로 모아놓고 그리고 MST가 완성되면 선택 안된 것들로 대체할 수 있는지 작업을 해보는 것이다. 선택 안된 것들로 대체해보고... 음 이것도 만만치 않네.. 일단 넘어가야겠다.




출처 : 백준님 강의, 백준님 강의 자료