[알고리즘] 프로그래머스 - 섬 연결하기

Evan·2025년 4월 14일

greedy

알고리즘

목록 보기

8/10

섬 연결하기

문제 설명

여러 개의 섬 사이에 다리를 놓아야 합니다.
모든 섬이 서로 통행 가능하도록 만들되, 다리 건설 비용의 총합이 최소가 되도록 해야 합니다.

예를 들어,
n = 4,
costs = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
이 경우 최소 비용은 4 (0-1, 0-2, 1-3 연결)

제한 사항

섬의 개수 n: 1 이상 100 이하
costs[i] = [a, b, cost]: 섬 a와 b를 cost의 비용으로 연결 가능
같은 연결은 중복되지 않으며, 연결 불가능한 경우는 없음
모든 섬은 반드시 연결 가능함

내가 접근한 방법

1. 비용이 적은 다리부터 정렬

먼저 모든 다리 정보(costs)를 비용 순으로 정렬

2. 연결된 섬 집합 만들기

처음엔 하나의 섬만 포함한 집합(connected)을 만듦
연결되지 않은 섬을 발견하면 다리를 놓고 집합에 포함시킴

3. 모든 섬이 연결될 때까지 반복

섬이 n개일 때, connected 집합의 크기가 n이 될 때까지 반복

import Foundation

func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    var total = 0
    var connected: Set<Int> = [costs[0][0]] // 시작 섬 하나만 포함
    let sorted = costs.sorted { $0[2] < $1[2] } // 비용 오름차순 정렬
    
    while connected.count < n {
        for node in sorted {
            let start = node[0]
            let end = node[1]
            let cost = node[2]

            // 하나는 연결되어 있고, 다른 하나는 아직 미연결일 때
            if connected.contains(start) && !connected.contains(end) {
                connected.insert(end)
                total += cost
                break
            }

            if connected.contains(end) && !connected.contains(start) {
                connected.insert(start)
                total += cost
                break
            }
        }
    }
    
    return total
}