문제
BOJ 10216 - Count Circle Groups
N개의 진영이 좌표와 통신 반경으로 주어졌을 때, 통신 범위가 겹치는 진영끼리 같은 그룹으로 묶어 그룹 수를 구하라.
입력
첫째 줄에 테스트 케이스 수, 각 케이스마다 N과 N개의 (x, y, r) 좌표가 주어진다.
출력
각 테스트 케이스마다 그룹 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 3 0 0 1 1 0 1 3 0 1 | 2 |
풀이
Union-Find로 통신 범위가 겹치는 진영들을 합친다.
- 모든 진영 쌍 (i, j)에 대해 두 원의 거리와 반경 합을 비교한다
- 두 원의 중심 거리의 제곱이 반경 합의 제곱 이하이면 통신 가능 (겹침)
- 겹치는 두 진영이 다른 집합이면 Union하고 그룹 수를 1 감소시킨다
- 경로 압축 기법으로 Find 연산을 최적화한다
- 최종 그룹 수를 출력한다
핵심 아이디어: 거리 비교 시 제곱근 계산 없이 양변을 제곱하여 정수 비교만으로 판단한다. Union-Find로 간접 연결까지 자동으로 처리된다.
코드
package day349;
import java.io.*;
import java.util.*;
public class Day337BOJ10216CountCircleGoup {
static int n, a[][], i, j, R, x, y, p[], X, Y, re;
static int P(int x) {
if (x == p[x])
return x;
return p[x] = P(p[x]);
}
static void u(int x, int y) {
x = P(x);
y = P(y);
p[x] = x < y ? x : y;
p[y] = x < y ? x : y;
}
public static void main(String[] args) throws Exception {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(r.readLine());
for (; n-- > 0;) {
re = i = j = Integer.parseInt(r.readLine());
p = new int[j];
a = new int[j][3];
for (; j-- > 0;) {
StringTokenizer t = new StringTokenizer(r.readLine());
a[j][0] = Integer.parseInt(t.nextToken());
a[j][1] = Integer.parseInt(t.nextToken());
a[j][2] = Integer.parseInt(t.nextToken());
p[j] = j;
}
for (x = 0; x < i; x++)
for (y = x + 1; y < i; y++) {
X = a[x][0] - a[y][0];
Y = a[x][1] - a[y][1];
R = a[x][2] + a[y][2];
if (X * X + Y * Y <= R * R)
if (P(x) != P(y)) {
re--;
u(x, y);
}
}
w.write(re + "\n");
}
w.flush();
}
}복잡도
- 시간: O(N^2 * α(N)) - 모든 쌍 비교 × Union-Find (α는 역아커만 함수)
- 공간: O(N) - 좌표 배열 및 부모 배열