[Algorithm/Programmers] 섬 연결하기 Swift

섬 연결하기 Level 3

문제 풀이:

 n개의 섬을 최소 비용으로 모든 섬이 통행이 가능하도록 만든다. -> 크루스칼 알고리즘을 이용한다. 

 

🍎 크루스칼 알고리즘 

• 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키는 것이다.

1. 비용을 기준으로 오름차순으로 정렬한다.

2. 간선을 차례로 확인하면서 사이클이 발생하는지 확인한다. 

2-1. 사이클이 발생하지 않으면 최소 신장 트리에 포함한다.

2-2. 사이클이 발생하면 PASS

3. 모든 간선에 대하여 2번을 반복한다. 

 

비용으로 정렬을 한 배열: [[0, 1, 1], [1, 3, 1], [0, 2, 2], [1, 2, 5], [2, 3, 8]]

같은 사이클인지 확인하기 위해서 Parent 배열을 만듭니다. 

집합에 포함되어 있지 않기 때문에 자기 자신으로 초기화한 상태입니다.

index	0	1	2	3	4
value	0	1	2	3	4

 

[0,1,1]에 대해서 섬 0과 섬 1의 parent value (집합)이 다르기 때문에(사이클이 없다는 뜻) Union을 한 상태입니다. 0과 1을 비교했을 때 0이 더 작기 때문에 섬 1의 Parent는 0이 됩니다.

index	0	1	2	3	4
value	0	0	2	3	4

 

마찬가지로, [1,3,1]에 대해서 섬 1과 섬 3의 parent value가 달라 다른 집합이기 때문에 Union을 합니다.

index	0	1	2	3	4
value	0	0	2	0	4

 

마지막으로, [0,2,2]에 대해서 섬 0과 섬 2의 집합을 합쳤습니다. 이 이후로는 사이클이 발생하기 때문에 섬을 연결하지 않습니다. 

index	0	1	2	3	4
value	0	0	0	0	4

 

코드:

import Foundation

func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    var result = 0
    var parent = [Int](repeating: 0, count: n+1)
    // 비용순으로 정렬
    let sortedCosts = costs.sorted { $0[2] < $1[2] }
    // 부모를 자기 자신으로 초기화
    for i in 1..<n+1 {
        parent[i] = i
    }
    
    for cost in sortedCosts {
    	// 사이클이 발생하지 않는 경우에만 집합에 포함
        if findParent(&parent, cost[0]) != findParent(&parent, cost[1]) {
            unionParent(&parent, cost[0], cost[1])
            result += cost[2]
        }
    }
    
    return result
}
// 섬이 포함되어 있는 집합 찾기
func findParent(_ parent: inout [Int], _ x: Int) -> Int {
    if parent[x] != x {
        parent[x] = findParent(&parent, parent[x])
    }
    return parent[x]
}
// 집합을 합치기
func unionParent(_ parent: inout [Int], _ a: Int, _ b: Int)  {
    let a = findParent(&parent, a)
    let b = findParent(&parent, b)
    
    if a < b {
        parent[b] = a
    } else {
        parent[a] = b
    }
}

print(solution(4, [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]])) // 4

 

문제:

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

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