[고득점 Kit(탐욕법)] 섬 연결하기 (Swift, Python)
코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 섬을 연결할 때 일단 가장 적은 비용의 다리를 먼저 사용해야 하므로 입력으로 주어진 costs를 비용을 기준으로 오름차순 정렬을 한다. 그 후 차례대로 다리를 사용해가면서 이미 연결된 두 섬에 대한 다리인지를 체크한다. 이미 두 섬이 연결되어 있으면 해당 다리를 사용하지 않고 넘어간다. 다리를 사용할때마다 몇 개의 다리를 사용했는지 체크한다. n개의 섬이 모두 연결되기 위한 최소 다리 개수는 n-1개이기 때문에 다리가 n-1개가 사용됐다면 탐색을 종료한다. 코드 [Swift] import Foundation var edges: [[Int]] = Array..
2022. 1. 2.
