백준 10216 (Count Circle Groups) - java

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

10216번: Count Circle Groups

 

문제 

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

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

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

 

유형 : 기하학 + Union - Find

 

접근 방식

• 두 지점이 통신 가능한지 확인하는 방법
  • (a.x - b.x)^2 + (a.y - b.y)^2 <= (a.r + b.r)^2
  • i번째 적군 진영을 입력받았을 때 1 ~ i-1지점의 적군위치들을 Union -Find 해주자

전체 코드

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

public class Main {
    static int n = 0;
    static int t = 0;

    static int[] root;

    static HashSet<Integer> set;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        t = Integer.parseInt(st.nextToken());

        for(int k = 1; k <= t; k ++){
            st = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(st.nextToken());

            root = new int[n+1];
            Node[] arr = new Node[n+1];
            for(int i=1;i<=n;i++){root[i] = i;}

            for(int i=1;i<=n;i++){
                st = new StringTokenizer(br.readLine(), " ");

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int z = Integer.parseInt(st.nextToken());

                arr[i] = new Node(x,y,z);

                for(int j=1;j<=i-1;j++){
                    if(i == j)
                        continue;

                    if(find(i) != find(j) && can(arr[i],arr[j])){
                        union(i,j);
                    }
                }
            }

            set = new HashSet<>();
            for(int i=1;i<=n;i++){
               set.add(find(root[i]));
            }

            sb.append(set.size()+"\n");
        }

        System.out.print(sb);
        br.close();
    }

    static boolean can(Node a, Node b){
        double disX = (a.x - b.x);
        double disY = (a.y - b.y);

        double dis = (disX * disX) + (disY * disY);

        double rD = (a.r + b.r) * (a.r + b.r);

        if(dis <= rD)
            return true;

        return false;
    }

    static int find(int x){
        if(x == root[x])
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y)
            root[x] = y;

        else{
            root[y] = x;
        }

    }
}
class Node{
    int x;
    int y;
    int r;

    Node(int x,int y,int r){
        this.x = x;
        this.y = y;
        this.r = r;
    }
}