[BOJ] 백준 10216 - Count Circle Groups

백준 10216 - Count Circle Groups

---

각 적군의 진영에서 Ri 이내 거리에 포함되는 모든 지역을 통신영역으로 가진다면

진영의 좌표를 (Xi, Yi)라고 할 때 , 적군의 통신영역은 (Xi, Yi)를 중심으로 하며, Ri를 반지름으로 갖는 원이라는 것을 알 수 있습니다.

이를 통해, 적군의 진영(i, j)끼리 통신이 가능하기 위해서는 통신영역의 중심 즉, 

두 진영사이의 거리가 두 Ri, Rj 의 합보다 작아야 한다는 것을 알아야 합니다.

아래 그림을 통해 생각해봅시다.

위의 색칠된 부분이 두 원이 겹치는 부분으로 이 경우에 통신이 가능하다고 하며, 그림을 보면 알 수 있다시피 통신이 가능한 경우는

dist ((Xa, Ya) 와 (Xb, Yb) 의 거리) <= Ra + Rb 입니다.

또한, 통신이 불가능한 경우는 아래와 같이, 

dist ((Xa, Ya) 와 (Xb, Yb) 의 거리) > Ra + Rb 입니다.

두 원사이를 비교하는 공식을 사용하여 각 진영끼리 통신이 가능한 지를 판별하며 dfs를 사용해 통신지역을 구분하면 제한시간 내에 해결할 수 있습니다.

위를 이용한 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
     
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine()); // 테스트 케이스 입력
        for(int t=0; t<tc; t++) {
            int n = Integer.parseInt(br.readLine()); // 통신탑의 개수
            int[][] info = new int[n][3];
            for(int i=0; i<n; i++) {
                String[] s = br.readLine().split(" ");
                info[i][0] = Integer.parseInt(s[0]); // 통신탑 x좌표
                info[i][1] = Integer.parseInt(s[1]); // 통신탑 y좌표
                info[i][2] = Integer.parseInt(s[2]); // 통신탑 r값
            }
            boolean[] visit = new boolean[n]; // 방문했는지를 체크.
            int cnt = 0;
            for(int i=0; i<n; i++) {
                if(!visit[i]) {
                    dps(info, visit, i);
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
 
    private static void dps(int[][] info, boolean[] visit, int loc) {
        // TODO Auto-generated method stub
        visit[loc] = true;
        for(int i=0; i<info.length; i++) {
            if(!visit[i]) {
                // 두 점사이의 거리 : sqrt((Xa - Xb)^2 + (Ya - Yb)^2)
                double len = Math.sqrt(Math.pow(info[loc][0]-info[i][0], 2) + Math.pow(info[loc][1]-info[i][1],2));
                if(len <= info[loc][2] + info[i][2]) // 점 사이의 거리가 반지름의 합보다 작다면 통신 영역이므로, 재귀호출.
                    dps(info, visit, i);
            }
        }
    }
 
}