[알고리즘] Disjoint Sets 공부하기(1) - 백준 10216 Count Circle Groups

작성자	이재영
일 시	2024. 11. 19 (화) 18:00 ~ 21:00
장 소	복지관 B-128-1호
참가자 명단	임혜진,  장원준, 이재영, 성창민, 김명원
사 진

---

이번 포스팅에서는 백준 10216번 Count Circle Groups 문제를 풀어보았다. 이 문제는 Union-Find을 활용하여 해결하는 문제로, 좌표 평면에서 주어진 원들의 군집을 찾아내는 문제이다. 문제 풀이 과정을 코드와 함께 정리해보았다.

1. 문제 설명

문제

• nnn개의 원이 좌표 평면 위에 주어집니다.
• 각 원은 중심 좌표 (x,y)(x, y)(x,y)와 반지름 rrr로 정의됩니다.
• 두 원이 서로 겹치는 경우 같은 군집(group)에 속합니다.
• 주어진 ttt개의 테스트 케이스에 대해 각 테스트 케이스마다 원의 군집 개수를 출력해야 합니다.

입력

• 첫 줄: 테스트 케이스의 개수 ttt
• 각 테스트 케이스:
  • 첫 줄: 원의 개수 nnn
  • 다음 nnn줄: 각 원의 정보 x,y,rx, y, rx,y,r (중심 좌표와 반지름)

출력

• 각 테스트 케이스마다 원의 군집 개수를 출력합니다.

---

2. 문제 접근 및 풀이

핵심 아이디어

• 원들이 겹치는 관계를 그래프로 표현할 수 있다.
• Union-Find을 사용하여 원들이 속한 군집을 찾아내는 방식으로 해결한다.
  1. 원 i와 원 j가 겹친다면 같은 집합으로 합친다.
  2. 모든 원에 대해 군집을 계산한다.

두 원의 겹침 조건

두 원이 겹치는지 확인하려면

원1과 원2의 거리의 제곱의 크기가 (원1의 반지름 + 원2의 반지름)의 제곱 크기를 비교하여 원 사이 거리가 더 작다면 이는 겹치는 것을 판단한다.

 

여기서 제곱을 하는 이유는 점 사이의 거리 공식이 sqrt((x2 - x1)^2 + (y2 - y1)^2) 인데 이 제곱근 연산을 줄이기 위해서이다.

Union-Find 구조

1. Find 연산: 특정 원이 속한 군집의 대표 원소를 찾는다.
2. Union 연산: 두 원을 같은 군집으로 합친다.

---

3. 코드 구현

import sys
input = sys.stdin.readline

def find(x):
    if x == arr[x]:
        return x
    arr[x] = find(arr[x])
    return arr[x]

def union(a, b):
    root_a = find(a)
    root_b = find(b)

    if root_a != root_b:
        arr[root_b] = root_a


t = int(input())

for _ in range(t):
    n = int(input())
    xyr = [list(map(int, input().split())) for __ in range(n)]
    arr = [i for i in range(n)]
    
    for i in range(n-1):
        x, y, r = xyr[i]
        for j in range(i+1, n):
            x2, y2, r2 = xyr[j]
            if (x-x2)**2 + (y-y2)**2 <= (r+r2)**2:
                union(i, j)
    
    check = set()
    for i in range(n):
        check.add(find(i))
    
    print(len(check))

---

4. 코드 설명

1. find 함수:
   • 주어진 원이 속한 군집의 대표 원소(루트)를 반환한다.
2. union 함수:
   • 두 원의 루트를 비교하여 서로 다른 집합일 경우 합친다.
3. 겹침 여부 검사:
   • 모든 원 쌍을 순회하며 두 원이 겹치는지 확인하고, 겹칠 경우 union 연산을 수행한다.
4. 군집 개수 계산:
   • 모든 원에 대해 find를 호출하여, 고유한 군집의 대표 원소를 set에 추가한다.
   • set의 크기가 곧 군집의 개수가 된다.

---

이 문제는 Union-Find 알고리즘과 거리 계산을 결합해 효율적으로 군집을 찾는 방법을 익히기에 좋은 문제였다고 생각한다. 다음에는 더 복잡한 그래프 문제를 도전해 보고 싶다.