42861

날짜: 2022년 1월 31일 오후 5:51

코드

Algorithm/42861.py at main · Junroot/Algorithm

풀이

최소의 비용으로 연결하기 위해서는 n - 1개의 다리만 있으면 된다는 점을 파악해야된다. 나는 가장 짧은 간선부터 선택해보면서 사이클이 발생하지 않도록만 하면 최소 비용으로 연결이 될 것이라고 생각했다. 이를 위해서 최소 값을 찾아서 꺼내기 쉬운 우선순위 큐를 사용해봤다.

사이클이 발생하는지 확인하는 방법에 대해서 고민을 좀 했었다. 내가 사용한 방법은 서로 연결되어 있는 섬들의 집합을 ‘그룹’이라고 정의하고, 그 그룹을 대표하는 섬 하나를 ‘부모(parent)‘라고 정의했다. 처음에 시작할 때는 아무도 연결되어 있지 않으므로 각 섬의 부모는 자기자신이 되는 것이다. 이 방법은 두 개의 그룹이 연결 될 때, 하나의 부모로 통일 시키는 과정이 필요하다.change_parent() 함수를 참고하면 된다.

몰랐는데, 내가 사용한 방법이 Kruskal MST 알고리즘이라고 한다. 이 방법 말고 하나의 정점에서 시작해서 단계적으로 확장하는 방법도 있는데 이 방법을 Prim MST 알고리즘이라고 한다.

참고 자료: https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html