[삼성SW기출][백준] 17472. 다리만들기 2(Kruskal, unionFind)

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

17472번: 다리 만들기 2

크루스칼 알고리즘을 사용하는 MST 문제였습니다.

모든 섬을 연결하는 최소 길이의 다리들을 건설하는 문제입니다.

 

구현방법

1. 각 섬을 1번부터 차례대로 마스킹 해줍니다.(DFS)
2. 그 후, BFS적으로 건설할 수 있는 모든 다리를 건설하면서 다리정보를 리스트에 저장합니다.
3. 리스트의 다리 길이를 비용으로 오름차순 정렬해주고, 사이클을 형성하지 않고, 최소 거리의 다리들을 선택해줍니다.(크루스칼)

크루스칼 알고리즘을 사용하면 쉽게 구현할 수 있습니다. 또한 크루스칼 알고리즘에 사용되는 유니온파인드 알고리즘도 중요합니다.

저는 이번 문제를 통해 크루스칼과 유니온파인드 알고리즘을 배우고 구현했습니다.