[Python] 백준 17472. 다리만들기2

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

백준에 삼성A형 기출문제로 분류되어 있다.

 

검색이 통제된 시험장 가서는 절대 못 풀 것 같은 문제.

bfs로 라벨링하고 최소 거리 구하는 것까지는 혼자서 처리할 수 있었는데, union find 코드는 예전에 내가 쓴 코드 다시 보고 만들어야 했다.

 

문제를 풀기 위해 생각해야 할 개념은 크게 세 가지다.

1. 각 섬을 구분해 준다. (섬별로 Labeling 해 준다고 보면 된다)

2. 각 섬을 연결하는 최소거리를 구한다.

3. 각 섬끼리의 최소거리를 토대로 섬과 섬을 연결해서, 모든 섬이 연결되면 최소거리의 합을 리턴하고 연결되지 않으면 -1을 리턴한다.