백준 온라인 저지, 분리집합 / 10216번: Count Circle Groups (파이썬 / , 백준 골드문제)

문제

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

2차원 평면 위의 N곳에 적군의 진영이 설치되어 있다. 각 적군의 진영들은 진영마다 하나의 통신탑을 설치해, i번째 적군의 통신탑은 설치 위치로부터 R_i 이내 거리에 포함되는 모든 지역을 자신의 통신영역 A_i로 가지게 된다. 만약 임의의 통신영역 A_i와 A_j가 닿거나 겹치는 부분이 있다면 진영 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)이 주어진다. 주어지는 수는 모두 정수이다.

출력

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

제한

예제 입력 1

2
2
0 0 1
1 0 1
3
0 0 1
2 0 1
10 0 5

예제 출력 1

1
2

힌트

접근 방법

- 적군의 진영을 이중 반복문을 통해 서로 같은 그룹인지 확인한다.
- 같은 그룹임을 확인하면 낮은 인덱스 번호로 초기화하는 유니온 파인드를 활용한다.

코드

# https://www.acmicpc.net/problem/10216
# 접근 방법
# 적군의 진영을 이중 반복문을 통해 서로 같은 그룹인지 확인한다.
# 같은 그룹임을 확인하면 낮은 인덱스 번호로 초기화하는 유니온 파인드를 활용한다.
def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]


def find_group(x1, x2):
    parent1 = get_parent(x1)
    parent2 = get_parent(x2)
    if parent1 > parent2:
        parent[parent1] = parent2
    else:
        parent[parent2] = parent1



import sys, math
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
    n = int(input())
    array = [list(map(int, input().split())) for _ in range(n)]
    parent = [i for i in range(n)]
    for i in range(n):
        x1, y1, r1 = array[i]
        for j in range(i+1, n):
            x2, y2, r2 = array[j]
            if math.sqrt((x1-x2)**2 + (y1-y2)**2) <= r1+r2:
                find_group(i, j)
    count_group = set()
    for i in range(n):
        x = get_parent(i)
        if x not in count_group:
            count_group.add(x)

    print(len(count_group))