[프로그래머스 Level3] 섬 연결하기 with 파이썬

문제

https://programmers.co.kr/learn/courses/30/lessons/42861

풀이

가중치를 기준으로 정렬하는 건 알겠는데 방문한 노드들을 처리하는 부분이 어려웠다. Kruskal's 알고리즘을 적용하면 쉽게 풀 수 있다.

크러스컬 알고리즘이란 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것이다.

적용하는 방법은 다음과 같다. 일단 가중치인 cost를 기준으로 배열을 정렬한다. 그러면 cost가 낮은 순서대로 정렬될 것이기 때문에 앞에서부터 찾아서 다리를 만든다면 최적의 해를 구할 수 있을 것이다.

그 다음, 연결된 섬들을 체크할 수 있는 세트(set)를 만든다. 세트는 중복을 제거하기 때문에 앞에서 최적의 cost로 섬들을 이미 연결했다면 싸이클이 형성되지 않도록 체크한다. 만약에 세트안에 이미 두 개의 노드들이 이미 들어있다면 continue 하면 된다. 그렇지 않은 경우에는 해당 노드들을 방문처리하고 cost를 정답에 더하면 된다.

코드