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

문제

방향성이 없는 그래프 G가 주어진다. 문제는 G의 최소 스패닝 트리보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다.

MST와 second MST의 모습

문제풀이

사용한 알고리즘: MST, LCA


 두번째로 작은 스패닝트리 (이하 SST) 를 찾는 문제였습니다.
 SST는 MST보다 커야 합니다. (같으면 안됩니다.)
 이 문제는 많이 까다로운 문제로 집중해서 읽어주세요....
 ( 정리한다고 정리했는데.... 제 생각이 정확히 전달 되는 글이었으면 좋겠습니다. )

(0) 생각

 우선 MST 를 만들고, MST 만드는데 사용되지 않은 간선들을 저장합니다.
 SST 를 만들기 위해서는 쓰지 않은 간선 중 하나를 MST 에 추가하고, 

 기존 MST 간선 중 하나를 제거해야 하는 것을 생각할 수 있습니다.

 a, b 노드를 연결하는 쓰지않은 간선을 추가하는 경우, 

 해당 간선부터 a, b 의 최소공통조상까지 cycle이 발생함을 알 수 있습니다. 

 다시 말해 a, b 노드의 공통 조상까지 연결된 간선들 중 하나를 제거하면 됩니다.

 제거해야 하는 기존 간선은 cycle 안의 간선 중 가장 큰 간선 이며 

 추가되는 간선과 값이 같아서는 안된다 를 생각할 수 있습니다.
( 값이 같을 경우 새로생긴 ST값 = MST 값 이 됩니다. SST는 MST와 같으면 안됩니다. )

 쓰지 않은 모든 간선들을 넣어보고, 위 방법을 통해 기존 간선 하나를 빼보며 스패닝트리(이하ST) 를 만들어 봅니다. 이때 만들어지는 ST 값은 MST 값보다 크거나 같을 것입니다.

 위 과정으로 만들어지는 ST 중 MST 값보다 최소로 큰 ST 가 SST입니다.

(1) 코드 147~151

 문제 첫줄에 MST가 존재한다고 명시 했으나 출력 조건에는 MST가 존재하지 않는다면 -1 출력이라고 나와있습니다... 실제로 MST 가 존재하지 않는 TC가 주어집니다.

(2) 코드 10~18

 입력받는 모든 간선들을 struct로 저장해줍니다.
 이때 MST 구성에 쓰인지 여부를 판단하기위해 bool을 하나 만들어줍니다.

(3) 코드 19~37, 122~143

 MST 를 만들어줍니다.

(4) 코드 39~40, 138~140

 만들어진 MST로 LCA 돌리기 위해, 과정(4) 에서 MST 만들 때 노드들의 부모-자식 관계를 간선 가중치와 함께 저장해 둡니다.

(5) 코드 42~60, 149~179

 LCA 를 돌리기 위해 1을 root로 잡고 MST 의 노드들의 깊이를 정해줍니다.
 'parent[i][k] : i노드의 2^k번째 조상' 이라 설정하고 구해주었습니다.
 'Biggest[i][k] : i노드의 2^k번째 조상까지 갈 때까지 <가장 큰 간선, 두번째로 큰 간선>' 이라 설정하고 이를 구해줬습니다.
 쓰지 않은 간선이 들어오면, 제거할 기존 간선을 미리 구해 놓은 것입니다.
 ( '추가되는 쓰지 않은 간선' 과 '제거할 가장 큰 기존 간선' 의 값이 같을 경우를 대비해 두번째로 큰 간선을 구해두었습니다.)

(6) 코드 61~113,180~188

 쓰지 않은 간선들을 하나씩 넣고, 기존 MST 간선 중 적절한 간선을 찾아 제거해봅니다.
 적절한 간선이란, 쓰지 않은 간선이 추가될 때 만들어지는 cycle 안의 기존간선 중 가장 크면서 쓰지 않은 간선과 같지 않은 기존간선입니다.
 과정(6)에서 미리 만들어 놓은 Biggest[i][k] 를 통해 적절한 간선을 찾습니다.