[Swift - 프로그래머스] 섬 연결하기

🕵🏻  문제 해석 

---

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2 이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

 

🤔 풀이 과정

---

섬과 섬을 연결하는 다리를 놓아 모든 섬이 최소 비용으로 연결될 수 있도록 하는 문제입니다. 즉, MST(Minimum Spanning Tree) 문제인데요. 그래프 이론에서 Spannig Tree는 모든 노드를 연결하는 부분 그래프라고 표현합니다. 이러한 그래프 중 최소 비용으로 모든 노드를 연결한 부분 그래프를 MST라고 부릅니다. 이 MST는 프림 알고리즘이나 크루스칼 알고리즘을 통해 다항 시간 안에 찾을 수 있습니다.

저는 프림 알고리즘을 이용하여 문제를 해결해보았습니다. 그래프는 인접 행렬 형태로 구현하고 0번째 섬을 시작점으로 최소 힙에 인접한 섬들과 비용을 튜플로 묶어 넣어주었습니다. 최소 비용 간선으로 포함된 섬들을 따로 집합을 이용하지 않고 tree 배열을 통해 체크해주었습니다. 최소 힙의 경우 따로 구현하지 않고 배열을 이용하여 매번 정렬해주는 방식으로 해결하였습니다.

프림 알고리즘과 크루스칼알고리즘은 따로 정리하여 알고리즘 포스팅으로 올려보도록 하겠습니다. 😄

 

📦  문제 풀이 & 코드

---

import Foundation

func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    var graph = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
    var tree = [Bool](repeating: false, count: n)
    var mstCost = 0
    // 최소힙역할 배열
    var pq: [(cost: Int, idx: Int)] = []
    
    for info in costs {
        let from = info[0]
        let to = info[1]
        let cost = info[2]
        
        graph[from][to] = cost
        graph[to][from] = cost
    }
    
    // 0번째 섬을 시작점으로 하고 트리에 넣어준 뒤 
    // 최소힙에 인접한 섬의 연결비용과 섬의 인덱스를 넣어준다.
    
    tree[0] = true
    
    for idx in 0..<n {
        if graph[0][idx] != 0 {
            pq.append((graph[0][idx], idx))
        }
    }
    
    while !pq.isEmpty {
        // 비용을 기준으로 오름차순 정렬
        pq.sort{$0.cost < $1.cost}
        
        let cur = pq.first!.idx
        let curCost = pq.first!.cost
        
        pq.removeFirst()
        
        // tree에 포함되어있지 않다면 추가하고 최소힙에 인접한 섬들을 넣어준다.
        
        if tree[cur] == false {
            tree[cur] = true
            // 최소 비용 추가
            mstCost += curCost
            for idx in 0..<n {
                if tree[idx] == false && graph[cur][idx] != 0 {
                    pq.append((graph[cur][idx], idx))
                }
            }
        }
    }
    
    return mstCost
}

• 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 

👍🏻  참고

---

• https://ko.wikipedia.org/wiki/프림_알고리즘