[BOJ] 백준 10216번 Count Circle Group (Java)

#10216 Count Circle Group

난이도 : 골드 5

유형 : 기하학 / 유니온 파인드

10216번: Count Circle Groups

▸ 문제

백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었다.

2차원 평면 위의 N곳에 적군의 진영이 설치되어 있다. 각 적군의 진영들은 진영마다 하나의 통신탑을 설치해, i번째 적군의 통신탑은 설치 위치로부터 Ri 이내 거리에 포함되는 모든 지역을 자신의 통신영역 Ai로 가지게 된다. 만약 임의의 통신영역 Ai와 Aj가 닿거나 겹치는 부분이 있다면 진영 i와 진영 j는 직접적으로 통신이 가능하다. 물론 직접적으로 통신이 가능하지 않더라도, 임의의 지역 i와 j가 중간에 몇 개의 직접통신을 거쳐서 최종적으로 통신이 가능하다면 i와 j는 상호간에 통신이 가능한 것으로 본다.

적들은 영리해서, 상호간에 통신이 가능한 부대끼리는 결집력있는 한 그룹처럼 행동한다. 백준은 이러한 그룹의 개수를 알아내 아군의 전략지침에 도움을 주고자 한다. 군대에 가서도 코딩하는 불쌍한 백준을 위해 적군의 통신망 분석을 도와주자!

▸ 입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각각의 테스트 케이스에 대해서 적군 진영의 숫자 N (1 ≤ N ≤ 3,000)이 주어진다. 이어서 N줄에 걸쳐 적군 진영의 좌표 x, y (0 ≤ x, y ≤ 5,000), 그리고 해당 진영의 R (0 ≤ R ≤ 5,000)이 주어진다. 주어지는 수는 모두 정수이다.

▸ 출력

각 테스트 케이스에 대해서 한 줄에 걸쳐 적군 진영의 그룹 개수를 출력한다.

 

문제 풀이  

두 통신 영역이 접점을 가지거나 겹치게 되는 경우는 한 그룹이라고 판단한다. 그래서 총 몇개의 그룹으로 이루어져있는지 찾아주면 되므로 Union-find를 사용해주면 된다. Union과정을 해야 할 경우만 파악해주면 된다.

 

두 원이 접점을 가지거나 겹치게 될 경우는 다음과 같다.

• (x1-x2)^2 + (y1-y2)^2 <= (r1+r2)^2

 

두 원이 겹치게 될 경우

 

 

다음의 조건에 해당하는 두 원을 합쳐주면 된다. 최대의 갯수는 3,000개 이므로 브루트 포스하게 모든 경우를 탐색해도 상관없지만 좀 더 효율적으로 탐색하는 방법은 현재 원 i를 기준으로 i보다 큰 j만을 탐색해주는 방법이 있다.

• 단, 위상을 정하여 작은 인덱스가 무조건 부모로 오게하든 큰 인덱스가 부모로 오게하든 정해줘야 한다.
  • 왜냐하면 다른 두 그룹이 합쳐지게 될 경우 작은 인덱스 기준으로 하면 값 설정이 제대로 초기화가 안될 수도 있기 때문이다.
• 아니면, 그룹 갯수를 판단할 때, find()메서드를 잘 활용해줘도 된다.

 

직관적인 것은 전자의 방식이지만 후자가 더 간단하다. 그룹 넘버를 확인할 때 find()메서드로 감싸주면 되기 때문이다.

Set<Integer> set = new HashSet<>();
for(int num : parents) {
	set.add(find(num)); // X -> set.add(num);
}
System.out.println(set.size());

 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	static class Circle{
		int x;
		int y;
		int r;
		
		public Circle(int x, int y, int r) {
			this.x = x;
			this.y = y;
			this.r = r;
		}
		
	}
	
	static int[] parents;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		while(tc-- > 0) {
			int n = Integer.parseInt(br.readLine());
			Circle[] circles = new Circle[n];
			for(int i=0; i<n; i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int r = Integer.parseInt(st.nextToken());
				
				circles[i] = new Circle(x, y, r);
			}
			
			parents = new int[n];
			for(int i=0; i<n; i++) {
				parents[i] = i;
			}
			
			for(int i=0; i<n; i++) {
				for(int j=i+1; j<n; j++) {
					Circle c1 = circles[i];
					Circle c2 = circles[j];
					
					if(find(i) == find(j)) continue;
                    
					int r = (int) Math.pow(c1.r+c2.r, 2);
					int dis =  (int) (Math.pow(c1.x-c2.x, 2)+Math.pow(c1.y-c2.y, 2));
					if(r >= dis) {
						union(i, j);
					}
				}
			}
			
			Set<Integer> set = new HashSet<>();
			for(int num : parents) {
				set.add(find(num));
			}
			System.out.println(set.size());
		}
	}
	
	static int find(int x) {
		if(x == parents[x]) return x;
		return parents[x] = find(parents[x]);
	}
	
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		parents[y] = x;
	}
}