[10216] Count Circle Groups

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

10216번: Count Circle Groups

기하학이 한 방울 들어간 유니온 파인드 문제. 이전에 풀다가 포기했던 문제다. 거리 계산 부분에서 아무 생각 없이 2차원 배열로서의 거리로 접근했는데, 옳은 방법이 아니었다. 2차원 배열 없이 풀 수 있는 문제.

풀이

입력되는 좌표와 범위를 입력받을 때마다, 모아놓은 나머지 지점들과의 거리를 계산, 범위가 겹치는 경우 유니온을 수행하여 마지막에 그룹의 개수를 출력하면 된다.
이번에는 그룹의 노드 개수를 파악하는 문제는 아니므로, 합병 수행 시 루트의 값은 바꾸지 않고 자식으로 들어갈 노드의 번호만 루트의 번호로 바꾸어 주면 된다.
두 지점의 범위 판정은 간단하다. 두 원점 사이의 거리가 두 지점의 범위의 총합보다 같거나 짧은 경우, 범위가 겹치는 것으로 판단하면 된다.

정답 코드

	import Foundation
	func dist(x1:Double, x2:Double, y1:Double, y2:Double) -> Double{
	return sqrt(((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)))
	}
	var output = ""
	for _ in 0..<Int(readLine()!)!{
	let n = Int(readLine()!)!
	var arr = Array(repeating: -1, count: n)
	var map = [(x:Double,y:Double,r:Double)]()
	func root(of n:Int) -> Int{
	if arr[n]<0 {return n}
	arr[n] = root(of: arr[n])
	return arr[n]
	}
	func union(a:Int, b:Int){
	let rootOfA = root(of: a)
	let rootOfB = root(of: b)
	if rootOfA == rootOfB{ return }
	arr[rootOfB] = rootOfA
	}
	for i in 0..<n{
	let info = readLine()!.split(separator: " ").map{Double($0)!}
	let x = info[0]
	let y = info[1]
	let r = info[2]
	map.append((x,y,r))
	for k in 0..<i{
	let target = map[k]
	if target.r + r >= dist(x1: target.x, x2: x, y1: target.y, y2: y){
	union(a: i, b: k)
	}
	}
	}
	var ans = 0
	for i in 0..<n{
	if arr[i]<0{
	ans += 1
	}
	}
	output += "\(ans)\n"
	}
	print(output)

view raw 10216.swift hosted with ❤ by GitHub