Sign in Subscribe
PS

[PS] BOJ 10216 / Count Circle Groups

Minjun Kim

• 3 min read
[PS] BOJ 10216 / Count Circle Groups
Thumbnail: Photo by Barnabas Hertelendy (Unsplash)
문제 링크: https://www.acmicpc.net/problem/10216

분리 집합을 활용하는 문제입니다.

풀이

분리 집합 활용해 그룹 합치기

각 부대의 연결 관계를 파악하며, 만약 두 부대의 통신 영역이 닿거나 겹칠 경우 분리 집합을 사용해 같은 집합으로 합쳐주면 됩니다.

두 부대가 연결되는 경우

각 부대는 중심 좌표 $(x, y)$와 통신 영역의 반지름 $R$이 주어집니다. 두 부대의 통신 영역이 닿거나 겹치기만 하면 두 부대는 서로 통신할 수 있습니다.

두 부대의 통신 영역이 닿거나 겹치는지 확인하려면, 두 부대의 중심 좌표가 두 부대의 통신 영역의 반지름의 합보다 같거나 작으면 됩니다. 실수 연산의 부정확성을 고려해, 거리는 유클리드 거리의 제곱을 활용해 비교했습니다.

enemy_base = [None] * 3000 # tuple[int, int, int] (x, y, R)

def is_connected(i, j):
    d2 = (enemy_base[i][0] - enemy_base[j][0]) ** 2 + (enemy_base[i][1] - enemy_base[j][1]) ** 2
    R2 = (enemy_base[i][2] + enemy_base[j][2]) ** 2
    return d2 <= R2

두 부대가 서로 통신 가능한지 판단하기

분리 집합을 통해 두 부대를 같은 그룹으로 합치기

분리 집합을 활용한 Union-Find 알고리즘을 사용해, 만약 두 부대가 서로 통신 가능하다면 (is_connected), union 연산을 통해 같은 그룹에 두면 됩니다.

roots = [i for i in range(3000)]

# Union - Find

def find_root(x):
    path = []
    while x != roots[x]:
        path.append(x)
        x = roots[x]

    for p in path:
        roots[p] = x
    
    return x

def union(x, y):
    x = find_root(x)
    y = find_root(y)

    if x == y:
        return False # 이미 같은 집합

    # 더 작은 수를 루트 노드로 정함
    if x > y:
        roots[x] = y
    else:
        roots[y] = x
    
    return True

def is_connected(i, j): ...

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

    # 입력 받고 배열 초기화하기
    for i in range(N):
        roots[i] = i
        enemy_base[i] = tuple(map(int, input().split())) # (x, y, R)

    # 임의의 두 부대가 서로 연결되는지 판단하기
    for i in range(N):
        for j in range(N):
            if i != j and is_connected(i, j):
                # 두 부대의 통신 영역이 서로 닿거나 겹치므로, 같은 그룹에 둔다.
                union(i, j)

분리 집합을 활용해 두 부대를 합치는 코드

답 구하기

이후, roots 배열을 순회하며 배열의 인덱스와 값이 같은 노드들의 수를 세면 됩니다.

인덱스와 값이 같은 노드들이 바로 분리 집합의 루트 노드들이며, 인덱스와 값이 다른 노드의 경우 다른 노드가 루트로 있는 집합에 속한 경우입니다.

for _ in range(int(input())):
    N = int(input())
    ... # 입력 받고 부대 연결 관계 구하는 과정 (위 코드)
    
    base_cnt = 0
    for i in range(N):
        if roots[i] == i:
            base_cnt += 1

    print(base_cnt)

답 구하기

전체 코드

input = open(0).readline
enemy_base = [None] * 3000
roots = [i for i in range(3000)]
base_cnt = 0

# Union - Find

def find_root(x):
    path = []
    while x != roots[x]:
        path.append(x)
        x = roots[x]

    for p in path:
        roots[p] = x
    
    return x

def union(x, y):
    x = find_root(x)
    y = find_root(y)

    if x == y:
        return False # 이미 같은 집합

    # 더 작은 수를 루트 노드로 정함
    if x > y:
        roots[x] = y
    else:
        roots[y] = x
    
    return True

def is_connected(i, j):
    d2 = (enemy_base[i][0] - enemy_base[j][0]) ** 2 + (enemy_base[i][1] - enemy_base[j][1]) ** 2
    R2 = (enemy_base[i][2] + enemy_base[j][2]) ** 2
    return d2 <= R2

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

    for i in range(N):
        roots[i] = i
        enemy_base[i] = tuple(map(int, input().split())) # (x, y, R)
    
    for i in range(N):
        for j in range(N):
            if i != j and is_connected(i, j):
                union(i, j)
    
    base_cnt = 0
    for i in range(N):
        if roots[i] == i:
            base_cnt += 1

    print(base_cnt)

solution.py