[BOJ] 백준 4386 별자리 만들기 (Swift)

문제

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

4386번: 별자리 만들기

풀이

좌표 평면에서 MST를 만드는 문제입니다.
간선이 주어지지 않았기 때문에 직접 간선을 구해주어야 합니다.

두 별 사이의 모든 거리를 구해주어야 합니다.
프로퍼티로는 시작노드, 도착노드, 비용을 갖는 Edge 구조체를 선언해주었습니다.

두 별 사이의 모든 거리를 구해주고, 구조체 배열에 넣어줍시다.

이제 크루스칼 알고리즘을 사용하여 최소 비용을 구할 수 있습니다.
거리를 기준으로 오름차순으로 정렬한 후, 사이클을 이루지 않는다면 이어주고 비용을 누적해서 더해줍시다.

누적된 비용이 답이 됩니다.

소스코드

	import Foundation
	typealias Coord = (x: Double, y: Double)
	struct Edge {
	let start: Int
	let end: Int
	let cost: Double
	}
	let n = Int(readLine()!)!
	var coords: [Coord] = []
	var edges: [Edge] = []
	var parent = [Int](0...n)
	for _ in 0..<n {
	let input = readLine()!.split(separator: " ").map { Double($0)! }
	let x = input[0], y = input[1]
	coords.append((x, y))
	}
	for i in 0..<n - 1 {
	for j in i + 1..<n {
	let cost = getDistance(coords[i].x, coords[i].y, coords[j].x, coords[j].y)
	edges.append(Edge(start: i + 1, end: j + 1, cost: cost))
	}
	}
	edges.sort { $0.cost <$1.cost }
	var answer: Double = 0
	for edge in edges {
	if !isSameParent(edge.start, edge.end) {
	union(edge.start, edge.end)
	answer += edge.cost
	}
	}
	print(answer)
	func getDistance(_ x1: Double, _ y1: Double, _ x2: Double, _ y2: Double) -> Double {
	return sqrt(pow(abs(x1 - x2), 2) + pow(abs(y1 - y2), 2))
	}
	func find(_ x: Int) -> Int {
	if parent[x] == x {
	return x
	}
	parent[x] = find(parent[x])
	return parent[x]
	}
	func isSameParent(_ a: Int, _ b: Int) -> Bool {
	return find(a) == find(b)
	}
	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
	}
	}

view raw 별자리 만들기.swift hosted with ❤ by GitHub

후기

문제에서 간선이 주어지지 않았기에 직접 간선을 만들어줘야 했던 문제였습니다.
접근만 한다면 어렵지 않게 풀 수 있는 문제였습니다.