[알고리즘/Swift] 1197 최소 스패닝 트리
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 1197 최소 스패닝 트리
- 제출 언어: Swift
- 알고리즘 분류:
- 그래프 이론
- 최소 스패닝 트리
풀이
최소 스패닝 트리
- 그래프 내의 모든 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]) 로 경로를 압축하지 않으면 시간복잡도가 커지는 것 주의!`
- 해당 target값의 parent가 target값과 같을 경우) 초기화해준 상태 그대로이므로, 가장 root node임을 알 수 있다.
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)