[Python] 10216번 Count Circle Groups

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

10216번: Count Circle Groups

---

 

22/09/20

 

 

전형적인 분리 집합 문제로, 분리 집합에 대한 내용만 잘 알고 있다면 쉽게 풀 수 있는 문제이다.

 

만약 분리집합을 모른다면 조금 푸는데 힘들 것이다.

---

 

문제 접근 방식:

 

 

문제에서는 통신영역이 서로 닿거나 겹치면 통신이 가능하다고 보는데, 여러 다리를 거쳐서 통신이 되는 것도 통신이 가능하다고 간주하였다.

 

때문에 이 정보를 보고 바로 분리 집합에 관련된 문제이겠구나,라고 생각을 했다.

 

적군 진영의 통신탑의 위치가 주어져 있고, 통신 거리가 주어져 있으므로, 통신영역이 서로 닿으려면 두 통신탑 사이의 거리가 두 통신탑의 통신 거리의 합보다 작거나 같아야 한다.

 

때문에 모든 통신탑의 조합을 돌아보며, 만약 저 조건을 만족시키면 유니온을 진행하고, 이후 간선의 단순화를 위해 파인드 함수를 전부 실행시키면 된다.

 

이후 그래프를 set에 넣어서 그 길이를 출력하는 방식으로 진행하였다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 10216번 Count Circle Groups
# 기하학, 자료구조, 분리집합
import sys
input = sys.stdin.readline
from itertools import combinations

T = int(input())
def find(node):
    if reps[node] != node:
        reps[node] = find(reps[node])
    return reps[node]
def union(node1, node2):
    rep1 = find(node1)
    rep2 = find(node2)
    reps[rep2] = rep1
for _ in range(T):
    n = int(input())
    reps = list(range(n+1))
    circles = [0] + [tuple(map(int, input().rstrip().split())) for _ in range(n)]
    for i, j in combinations(range(1, n+1), 2):
        circle1, circle2 = circles[i], circles[j]
        if (circle1[0] - circle2[0])**2 + (circle1[1] - circle2[1])**2 <= (circle1[2] + circle2[2])**2:
            union(i, j)
    for i in range(1, n+1):
        find(i)
    print(len(set(reps))-1)