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

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

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

 

 

문제를 간단하게 요약하면 각 노드를 모두 연결 할 수 있는 간선의 최소 가중치를 구해라 라는 문제에요

방문하는 문제와 결이 달라요

 

되게 어려운 문제지만 

크루스칼 알고리즘과

Union Find 알고리즘 개념을 알고나면 접근하기 쉬워지는 문제에요

 

Union Find 란

여러개의 노드가 존재 할 때 연결된 노드들을 같은 집합 구성원으로 묶어주는 알고리즘이에요

 

[1,2], [2,3], [3,4], [5,6] 이런 집합이 있다면

위와 같이 그려 볼 수 있겠죠?

2번과 4번이 같은 집합인지 확인하려면 탐색을 통해서 찾아야하구요..

하지만 

union find알고리즘을 한다면

 

 

위와같은 그림으로 구성되요

최상위 부모를 모두가 가르키고 있기 때문에 누가 어떤 그룹에 속하는지를 알 수 있죠

 

 

크루스칼 알고리즘은

최소 스패닝 트리(MST)로 가중치 값이 가장 최소인 그래프를 찾는 알고리즘이에요

탐욕(그리디) 알고리즘이죠

 

각 노드들의 정보(정점과 비용)을 저장하고

정보를 오름차순으로 정렬하고 

싸이클이 생기지 않으면 그래프에 추가하는 방식이에요

싸이클을 확인하는 방법은 추가하려는 각 정점이 같은 집합인지를 확인하면 되구요

 

제가 크루스칼을 이해할때 참고한 블로그에요

gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

 

이를 이용해서 코딩테스트 문제를 해결 할 수 있어요

 

풀이방법

부모를 저장할 배열과

비용을 정렬한 배열을 만들고

 

비용을 정렬한 요소를 순서대로 접근해요 ( 최소비용부터 차례대로 접근 )

각 정점이 같은 그룹에 속하지 않았다면 <- (findSet을 통해 탐색)

그 비용을 더해주고

그 두 정점을 같은 그룹으로 만들어주는 과정(unionSet)을 반복해요

 

 

import Foundation

func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    var parents: [Int] = (0...n-1).map{ $0 }
    let costs = costs.sorted { $0[2]<$1[2] }
    
    /// 최상위 부모 등록
    func unionSet(start: Int, end: Int) {
        var start = start
        var end = end
        
        start = findSet(start)
        end = findSet(end)
        if start != end {
            parents[end] = start
        }
    }
    
    /// 자신의 최상위 부모찾는 함수
    func findSet(_ start: Int) -> Int {
        if parents[start] == start {
            return start
        } else {
            // 자신이 최상위 부모가아니라면 최상위 부모를 찾는 재귀실행
            let parent = findSet(parents[start])
            parents[start] = parent
            
            // 자신을 부모로 가지고 있는 노드들 전부 새로운 부모로 업데이트
            for i in 0..<parents.count {
                if parents[i] == start {
                    parents[i] = parent
                }
            }
            
            return parent
        }
    }
    var result = 0
    for cost in costs {
        let start = findSet(cost[0])
        let end = findSet(cost[1])
        let value = cost[2]
        
        if start != end {
            result += value
            unionSet(start: start, end: end)
        }
    }
    
    return result
}