[백준 1197] 최소 스패닝 트리 (Swift)

https://www.acmicpc.net/problem/1197

크루스칼 알고리즘

가중치 그래프의 간선 정보 ("노드1, 노드2, 가중치")가 배열로 주어지고, 모든 정점을 잇는 간선의 가중치 합이 최소가 되는

최소 스패닝 트리의 가중치 합을 구하는 문제

 

접근방법

처음에 다익스트라로 풀었다가 프림으로 풀었다가 안돼서 결국 크루스칼로 풀었다.

 

크루스칼 알고리즘의 핵심은

1. 간선을 가중치 순으로 오름차순 정렬한다.

2. 최소 간선 부터 살펴보면서 (담으면서) 선택된 간선에 의해 이어진 노드들의 부모노드를 통일시킨다.

3. 이때, 간선을 선택할 때는 현재 이미 이어져있는 간선들에 연결된 노드들과 사이클을 형성하지 않도록 하는 조건을 건다.

인데 이를 위해서는 

 

1. [가중치, 노드1, 노드2]를 원소로 갖는 배열을 가중치 기준으로 정렬해야한다 (커스텀 정렬)

2. 각 노드의 부모노드를 저장하고 있는 parents 배열을 선언하고, 처음에는 본인의 부모노드는 본인이 되도록 초기화한다

3. 임의의 두 노드의 부모노드를 통일시키는 함수 union과 전달받은 노드의 부모를 찾는 함수 findParent를 정의한다

3. 정렬된 간선 배열을 차례로 순환하면서 해당 간선이 잇고 있는 두 노드의 부모가 각각 다른 경우에만 해당 간선을 선택한다.

3-1. 선택하면, 두 노드는 union 함수에 의해 부모가 통일되고, 선택된 간선 수를 저장하는 변수 lineCnt 값이 1 증가 (lineCnt가 V-1개가 되면 반복문 종료), 가중치 합을 담고있는 result 변수에 해당 간선의 가중치 값이 추가된다.

4. result 출력하면 끝

 

오답노트

union 함수에서 두 노드의 부모노드 중 적은 수로 두 부모노드의 부모노드가 통일되어야 한다.

처음에는 단순히 두 자식의 부모노드 값 중 최소를 찾아서

그 자식들의 부모노드 값을 그 자식들의 부모노드 중 작은 값으로 입력해줬는데 틀렸었다.

자식의 부모노드 값을 수정하는게 아니라 자식의 부모노드의 부모노드 값을 수정하는건, 자식의 부모노드만 바뀌면 근본적인 부모노드에 반영이 안되기 때문인걸 깨달았다.

 

+ 백준에서 swift로 풀이할 때 안에 func 쓰려면 겉에 큰 solution 함수로 묶은다음에 사용하는 게 오류가 안났다.

 

소스코드

import Foundation

func solution() -> Int {
    var inputs:[Int] = readLine()!.split(separator: " ").map { Int($0)! }
    let V = inputs[0]
    let E = inputs[1]

    // process
    // 간선들 [[가중치,node1, node2]]
    var edges:[[Int]] = []

    for i in 0..<E {
        var line:[Int] = readLine()!.split(separator: " ").map { Int($0)! }
        edges.append([line[2], line[0], line[1]])
    }

    // 간선들 가중치 기준 오름차순 정렬
    edges.sort { a, b in
        return a[0] < b[0]
    }

    // parents 배열 초기화 (부모 = 본인)
    var parents:[Int] = Array<Int>(repeating: 0, count: V+1)
    for i in 0...V {
        parents[i] = i
    }
    
    func findParent(_ index: Int) -> Int {
        if parents[index] == index {
            return index
        } else {
            parents[index] = findParent(parents[index])
            return parents[index]
        }
    }
    
    func union(a:Int, b:Int) {
        var a_parent = findParent(a)
        var b_parent = findParent(b)
        if a_parent < b_parent {
            parents[b_parent] = a_parent 
        } else {
            parents[a_parent] = b_parent
        }
    }
    
    var result = 0
    var lineCnt = 0
    for edge in edges {
        // 모든 정점을 담으면 반복문 종료
        if lineCnt == V-1 {
            break
        }
        // 부모가 같음 == 사이클 형성 -> 추가 X
        // 부모가 다를 때만 담기
        if findParent(edge[1]) != findParent(edge[2]) {
            result += edge[0]
            union(a: edge[1], b: edge[2])
            lineCnt += 1
        }
    }
    return result
}

print(solution())