[BOJ] 17472

다리 만들기 2

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

문제를 푸는 데에 필요한 알고리즘은 특별하지 않았지만 구현의 난이도가 좀 있었습니다.

먼저, 1로만 되어있는 섬들을 구분하기 위해서는 각 섬들에 ID를 붙여줘야 합니다.(1번섬, 2번섬, 3번섬, …)

다리를 만드는 것은 union find를 이용한 Kruskal algorithm을 사용하였습니다.

1. 각 섬에서 다른 섬들로 갈 수 있는 모든 다리의 후보들을 BFS 또는 DFS로 구하여 저장해줍니다.
2. 모든 다리의 후보들을 다리의 길이의 오름차순으로 정렬해줍니다.
3. 짧은 다리부터 확인하며 다리를 연결했을 때 사이클이 생기지 않는다면 그 다리를 연결해줍니다. 이렇게 한다면, 연결할 수 있는 경우에 최소한의 다리 길이로 모든 섬들이 연결됩니다.

연결이 끝난 후 섬들로 이루어진(union find의 결과물인)
tree의 루트가 하나라도 다른 것이 있다면 연결이 실패한 것이고,
모두 다 같은 root를 갖는다면 연결이 성공한 것입니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/17472.cpp