CEO

문제 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제 풀이 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 모든 섬이 통행 가능한 최소 비용을 구하는 문제이다. 이 문제는 전형적인 `Kruskal 알고리즘` 문제이다. 해당 알고리즘 자체가 사이클을 이루지 않고, 최소 비용을 찾는 것이다. 이와 마찬가지로 문제에서도 "다리를 여러 개 건너더라도 해당 섬에 방문할 수 있으면 된다."라는 조건이 주어진다. 따라서 각 노드의 비용(건설하는 비용)을 기준으로 정렬한 후, 방문 여부에 따라 현재의 비용을 갱신하면 된다. 주어진 예시를 Kruskal로 탐색하게 되면 위의 그림과 같은 순서로 탐색하게 된다. 따..