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

문제

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

1197번: 최소 스패닝 트리

풀이

문제 그대로 최소 스패닝 트리(MST)를 구하는 문제입니다.
최소 스패닝 트리를 구하는 방법으로는 크루스칼 알고리즘, 프림 알고리즘을 활용해서 구할 수 있습니다.

저는 크루스칼 알고리즘을 활용하여 풀이하였습니다.
간선을 비용의 오름차순 순으로 정렬하여, 비용이 적은것 부터 확인하면서 사이클이 이루어지지 않는다면 연결시켜 줍시다.

연결시킨 비용의 총 합이 가중치가 됩니다.

소스코드

	typealias Edge = (a: Int, b: Int, cost: Int)
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let v = input[0], e = input[1]
	var parent = [Int](0...v)
	var edges: [Edge] = []
	for _ in 0..<e {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let a = input[0], b = input[1], cost = input[2]
	edges.append(Edge(a, b, cost))
	}
	edges.sort { $0.cost <$1.cost }
	var answer = 0
	for edge in edges {
	let a = edge.a, b = edge.b, cost = edge.cost
	if !isSameParent(a, b) {
	union(a, b)
	answer += cost
	}
	}
	print(answer)
	func find(_ x: Int) -> Int {
	if parent[x] == x {
	return x
	}
	parent[x] = find(parent[x])
	return parent[x]
	}
	func union(_ a: Int, _ b: Int) {
	let a = find(a)
	let b = find(b)
	if a == b {
	return
	}
	if a > b {
	parent[a] = b
	} else {
	parent[b] = a
	}
	}
	func isSameParent(_ a: Int, _ b: Int) -> Bool {
	return find(a) == find(b)
	}

view raw 최소 스패닝 트리.swift hosted with ❤ by GitHub

후기

MST를 구하는 알고리즘에 대해 안다면 쉽게 풀 수 있는 문제였습니다.