[BOJ][🟡5][백준#10216] Count Circle Groups

문제 출처

BAEKJOON Online Judge #10216

문제

백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었다. 2차원 평면 위의 N곳에 적군의 진영이 설치되어 있다. 각 적군의 진영들은 진영마다 하나의 통신탑을 설치해, i번째 적군의 통신탑은 설치 위치로부터 Ri 이내 거리에 포함되는 모든 지역을 자신의 통신영역 Ai로 가지게 된다. 만약 임의의 통신영역 Ai와 Aj가 닿거나 겹치는 부분이 있다면 진영 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)이 주어진다. 주어지는 수는 모두 정수이다.

출력

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

예제

입력

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

출력

1
2

My Sol

import sys
input = sys.stdin.readline

def calcD(c1, c2):
    return ((c1[0]-c2[0])**2 + (c1[1]-c2[1])**2)

def dfs(i):
    for j in range(N):
        if i == j or visit[j]: continue
        if calcD(cs[i], cs[j]) > (cs[i][2]+cs[j][2])**2: continue
        visit[j] = 1
        dfs(j)

T = int(input())
for _ in range(T):
    N = int(input())
    cs = [list(map(int, input().split())) for _ in range(N)]
    cnt = 0
    visit = [0]*N
    for i in range(N):
        if visit[i]: continue
        dfs(i)
        cnt += 1
    print(cnt)

dfs를 이용하였다.

우선 한 원을 기준으로 어떠한 원 사이의 거리를 계산한 값이 두 원의 반지름의 합보다 작거나 같은 경우 한 그룹으로 취급할 수 있다. 때문에 해당 인접한 원을 찾게 되면 그 원으로부터 다른 원들의 인접 여부를 확인하는 방식으로 연쇄적으로 실시한다.

이때 한 번 확인한 원은 다시 확인하지 않기 위해 visit을 이용해 한 그룹을 모두 조회하는 경로의 원은 모두 visit을 체크하고 해당 dfs를 모두 마치면 한 그룹에 대한 조사를 마친 것이기 때문에 cnt를 1 추가해준다.

처음에는 원의 범위를 모두 1을 체크하며 완전탐색 + bfs를 해볼까 했는데, 그럴 경우에 맵의 크기가 5000x5000인데 다가 범위의 수가 3000으로 시간 복잡도에서 불가능한 방식이었다.

결과

맞았습니다!!

원과 원 사이의 인접 여부를 중심점의 좌표와 반지름으로 계산하는 방식까지는 고민하여 찾아내었으나, 알 수 없는 이유로 오류를 겪어 시간 초과가 발생하였다. 결국 블로그를 참고했는데, dfs 알고리즘을 사용했던 것이 조금 달랐다.

그런데 같은 dfs 알고리즘을 사용했는데도 자꾸 시간 초과가 나는 것이었다. 아이디어에서 힌트만 얻었을 뿐 코드를 그대로 가져오지 않았기 때문이다. 더 분석해보니, 길이를 구할 때 x 변화량의 제곱값과 y 변화량의 제곱값의 합의 제곱근이 거리인데, 나는 여기까지 calcD 함수에서 처리해준 반면, 블로그에서는 반지름의 합에 제곱을 취해준 것이다. 이것만 바꾸었는데 시간이 합격선이었다.

이것이 연산시간에 차이를 만들 것이라 생각치도 못했다. 너무 의외의 결과였다.

모범답안

출처

from functools import cmp_to_key
import copy
from itertools import combinations, permutations
from collections import deque, defaultdict
import heapq
import math
from bisect import bisect_left, bisect_right
from sys import stdin, stdout, setrecursionlimit, exit

INF = float('inf')
MOD = 1000000007


def uff(a):
    if parent[a] == a:
        return a
    parent[a] = uff(parent[a])
    return parent[a]


def ufu(a, b):
    pa = uff(a)
    pb = uff(b)
    if pa != pb:
        parent[pa] = pb


t = int(stdin.readline())
for _ in range(t):
    n = int(stdin.readline())
    parent = [i for i in range(n)]
    tower = []
    for i in range(n):
        x,y,r1 = map(int, stdin.readline().split())
        for j in range(i):
            a,b,r2 = tower[j]
            if (x-a)**2 + (y-b)**2 <= (r1+r2)**2:
                ufu(i,j)
        tower.append((x,y,r1))
            
    ans = set()
    for i in range(n):
        ans.add(uff(i))
    stdout.write(f"{len(ans)}\n")

연산시간이 절반에 해당하는 코드포스 블루 유저의 풀이를 분석해보려 한다. 온갖 특이한 라이브러리를 사용해 풀어내셨다.

우선 눈에 띄는 것은 유니온 파인드 알고리즘을 활용했다는 점이다. 한 원의 정보를 받으면, 이전까지의 원의 정보를 담은 tower 배열에서 각각의 원들을 비교한다. 만약 영역이 인접하거나 겹친다면 유니온파인드를 이용해 최상위 루트를 같게 처리해주었다.

이후 0부터 n-1까지의 인덱스에 대해 루트 노드 번호를 set에 넣어 중복을 제거한 원소들의 개수를 세어 출력하였다.

확실히 고수의 풀이가 느껴진다. 좋은 풀이였다.