문제 정보


image

풀이

최소 스패닝 트리

  • 그래프 내의 모든 node들을 최소의 간선 비용으로 연결하는 트리이다
  • cycle이 없는 조건일 경우 사용한다
  • Greedy를 이용한 그래프 탐색 알고리즘이다
  • Kruskal알고리즘과 Prim알고리즘 이 두 알고리즘으로 해결할 수 있다

Kruskal’s Alg

  • 1) 그래프 내의 모든 edge(간선)들을 비용에 따라 오름차순으로 정렬한다
  • 2) 1)에서의 edge들을 최소 스패닝 트리에 추가한다
  • 3) cycle을 형성하는 edge는 건너뛴다

Prim’s Alg

  • 1) 임의의 node를 시작 node로 설정
  • 2) 각 node마다 최소 스패닝 트리가 될 수 있는 최소 비용 값과 연결 정보를 가진다
  • 3) 가장 작은 최소 비용 값을 갖는 node에 방문한다
  • 4) 방문한 node의 인접 node들의 최소 비용 값과 연결 정보를 갱신한다
  • 최소 스패닝 트리가 cycle없이 모든 node를 연결할 때까지 3) ~ 4)를 반복한다

알고리즘 적용

Prim’s Alg와 유사한 DIJKSTRA 알고리즘을 최근에 풀었기 때문에 Kruskal’s Alg를 이용하여 풀었다
모든 Node들이 자신의 parent값을 나타내는 배열을 생성하여 자기 node의 값들을 넣어준다
이 후 모든 간선들을 돌면서 root(가장 상위 parent)값들이 같지 않은 tree들을 합치고 최소 비용에 더해준다
두 개의 tree를 합칠 경우 둘 중 더 작은 값을 가진 node가 상위 tree가 되도록 한다 -> 일정한 규칙을 정해져서 시간을 단축시킨 것 이므로 큰 값을 가진 tree가 상위 tree가 되어도 상관 없음

  • func find(_ target: Int)-> Int : 해당 target값을 가진 Node의 root값 반환
    • 해당 target값의 parent가 target값과 같을 경우) 초기화해준 상태 그대로이므로, 가장 root node임을 알 수 있다.
      -> 자기 자신의 값 target 반환
    • 그렇지 않을 경우) root node를 찾을 때까지 recursive 함수를 통해 계속 parent node에 접근한다
      ` parent[target] = find(parent[target]) 로 경로를 압축하지 않으면 시간복잡도가 커지는 것 주의!`
  • func union(_ a: Int, _ b :Int) : 두 개의 값을 가진 Node를 하나의 tree로 합친다
    • 줄줄이 일 자로 node가 연결되는 것을 막기 위해 특정한 기준(a<b)를 세워서 두 tree를 합침


전체 코드

import Foundation

func find(_ target: Int)-> Int{
    if parent[target] == target{
        return target
    }else{
        parent[target] = find(parent[target])
        return parent[target]
    }
}
func union(_ a: Int, _ b :Int){
    if a < b{
        parent[find(b)] = a
    }else{
        parent[find(a)] = b
    }
}

let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (V,E) = (n[0], n[1])
var weight: Int = 0
var edge: [[Int]] = Array()
var parent: [Int] = Array(0...V)
for i in 0..<E{
    edge.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

for e in edge.sorted(by: {$0[2] < $1[2]}){
    let (u,v) = (e[0], e[1])
    if find(u) != find(v){
        union(u,v)
        weight += e[2]
    }
}
print(weight)