[17250] 은하철도

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

17250번: 은하철도

유니온 파인드 문제다. 바로 이전 풀이 [11816] 로봇 조립 문제와 같은 방법으로 접근하면 풀 수 있다.

 

풀이

지난번 문제와의 차이점은 은하에 속한 행성의 개수가 처음부터 주어진다는 점이다. 배열 galaxy의 초기값을 0으로 설정하고 행성의 개수가 입력될 때 해당 값만큼 빼주고 시작하면 된다.

은하가 연결될 때마다 연결된 은하의 행성 수를 출력해야 하므로 유니온 함수에 결합 동작 이후 배열의 루트에 해당하는 값을 절댓값으로 출력하면 된다.

 

정답 코드

	import Foundation
	let nm = readLine()!.split(separator: " ").map{Int($0)!}
	let n = nm[0]
	let m = nm[1]
	var galaxy = Array(repeating: 0, count: n)
	for i in 0..<n{
	let size = Int(readLine()!)!
	galaxy[i] -= size
	}
	func root(of n:Int) -> Int{
	if galaxy[n] < 0{ return n }
	galaxy[n] = root(of: galaxy[n])
	return galaxy[n]
	}
	func union(a:Int, b:Int){
	let rootOfA = root(of: a)
	let rootOfB = root(of: b)
	if rootOfA == rootOfB {
	print(abs(galaxy[rootOfA]))
	}else if galaxy[rootOfA] <= galaxy[rootOfB]{
	galaxy[rootOfA] += galaxy[rootOfB]
	galaxy[rootOfB] = rootOfA
	print(abs(galaxy[rootOfA]))
	}else{
	galaxy[rootOfB] += galaxy[rootOfA]
	galaxy[rootOfA] = rootOfB
	print(abs(galaxy[rootOfB]))
	}
	}
	for _ in 0..<m{
	let ab = readLine()!.split(separator: " ").map{Int($0)!-1}
	union(a: ab[0], b: ab[1])
	}

view raw 17250.swift hosted with ❤ by GitHub