백준 10216 - Count Circle Groups

문제

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

풀이

• 접촉하는 범위(원)을 하나의 그룹의 지정하여 그 개수를 구하는 문제
• 원 형태로 주어지는 범위마다 인덱스를 부여하여 좌표와 함께 Area 클래스로 다룸
• parent배열을 활용해 Area 간 집합 관계 표현
  • parent[i]는 i번째 Area 의 부모 Area 인덱스를 저장함
  • parent[i]가 음수일 때는 부모가 없는 경우(루트), 음수로 랭크 표현
• 저장한 Area 목록을 순회하며 한 Area가 다른 Area와 접촉할 때(원의 중심 간 거리 <= 두 원의 반지름 합)
  • 파인드 연산을 통해 두 원의 루트를 탐색
  • 유니온 연산을 통해 두 원을 하나의 그룹으로 지정
• 로직의 시간 복잡도는 그룹을 지정하는 이중 for문에서 $O(N^2)$으로 수렴, 최대 $N=3000$이므로 테스트 케이스 개수를 고려해도 무난히 제한 조건 8초 통과

코드

import static java.lang.Integer.parseInt;

import java.awt.geom.Area;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {

    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(br.readLine());
        List<Long> answer = new ArrayList<>();

        while (T-- > 0) {
            int N = parseInt(br.readLine());
            parent = new int[N];
            Arrays.fill(parent, -1);

            List<Area> areas = new ArrayList<>();

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = parseInt(st.nextToken());
                int y = parseInt(st.nextToken());
                int r = parseInt(st.nextToken());

                areas.add(new Area(i, x, y, r));
            }

            for (Area area : areas) {
                for (Area area2 : areas) {
                    if (area.i == area2.i) {
                        continue;
                    }

                    if (!area.contactTo(area2)) {
                        continue;
                    }

                    int u = find(area.i);
                    int v = find(area2.i);

                    if (u == v) {
                        continue;
                    }

                    if (parent[u] < parent[v]) {
                        parent[u] += parent[v];
                        parent[v] = u;
                    } else {
                        parent[v] += parent[u];
                        parent[u] = v;
                    }
                }
            }

            long count = Arrays.stream(parent).filter(p -> p < 0).count();
            answer.add(count);
        }

        System.out.println(answer.stream().map(String::valueOf)
            .collect(Collectors.joining("\n")));
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0) {
            return u;
        }

        return parent[u] = find(parent[u]);
    }

    static double calculateDist(int x1, int y1, int x2, int y2) {

        return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
    }

    static class Area {

        int i, x, y, r;

        public Area(int i, int x, int y, int r) {
            this.i = i;
            this.x = x;
            this.y = y;
            this.r = r;
        }

        public boolean contactTo(Area area) {
            double dist = calculateDist(this.x, this.y, area.x, area.y);

            return dist <= this.r + area.r;
        }
    }
}

결과