https://www.acmicpc.net/problem/10216
10216번: Count Circle Groups
백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었
www.acmicpc.net
기하학이 한 방울 들어간 유니온 파인드 문제. 이전에 풀다가 포기했던 문제다. 거리 계산 부분에서 아무 생각 없이 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) |

'Problem Solving > BOJ' 카테고리의 다른 글
[16724] 피리 부는 사나이 (0) | 2022.12.13 |
---|---|
[20955] 민서의 응급 수술 (0) | 2022.12.12 |
[17250] 은하철도 (0) | 2022.12.10 |
[18116] 로봇 조립 (0) | 2022.12.09 |
[3190] 뱀 (0) | 2022.12.08 |