백준 10216 : Count Circle Groups (Python)

본문 링크

import sys,math
input=sys.stdin.readline

def Find(x):

    if disjoint[x]!=x:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a>b:
        disjoint[a]=b
    else:
        disjoint[b]=a

T=int(input())

for _ in range(T):
    N=int(input())

    disjoint=[ j for j in range(N) ]

    L=[ list(map(int,input().split())) for j in range(N) ]

    for j in range(N):
        X1,Y1,R1=L[j]
        for k in range(j+1,N):
            X2,Y2,R2=L[k]
            if math.sqrt((X1-X2)**2+(Y1-Y2)**2)<=R1+R2:
                Union(j,k)

    answer=set()
    for j in range(N):
        A=Find(j)
        if A not in answer:
            answer.add(A)
    print(len(answer))

📌 어떻게 접근할 것인가?

2차원 좌표에서 거리가 $R$ 일때 두 좌표가 같은지 확인하는 방법은 기하학적인 방법으로 찾을 수 있습니다.

• $math.sqrt((X1-X2)**2+(Y1-Y2)**2)<=R1+R2$

이후 이 공식을 통해서 두 지점이 같은 범위에 속하는지 판별 한 후에 유니온 파인드 알고리즘을 사용하면됩니다.