[백준] 10216번 Count Circle Groups 파이썬 코드

코드

# 주의해야할 점
# parent 배열은 루트 노드임을 항상 보장해주지는 않는다.

import sys, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

def find(a,lst):
  if a != lst[a]:
    lst[a] = find(lst[a], lst)
  return lst[a]

def union(a,b,lst):
  a = find(a, lst)
  b = find(b, lst)
  
  if a<b:
    lst[b] = a
  else: lst[a] = b

tc = int(input())

for _ in range(tc):
  n = int(input())
  parent = [i for i in range(n)]
  graph = [[*map(int,input().split())] for _ in range(n)]
  for i in range(n):
    x1,y1,r1 = graph[i]
    for j in range(i+1,n):
      x2,y2,r2 = graph[j]
      if math.sqrt((x2-x1)**2 + (y2-y1)**2)<= r1+r2:
        union(i,j,parent)
  res = set()
  for i in range(n):
    num = find(i, parent)
    if num not in res:
      res.add(num)
  print(len(res))

설계는 잘했는데 디테일이 부족한 것 + 이전에 했던 실수 반복이 틀린 이유가 됐다. 

 

1. 이중 for문을 이용해 전부 확인해주었어야 했는데 for문 하나만으로 해결하려고 해서 틀렸다. range(n-1)로 하고 그 다음 것만 봤던 것이 틀린 첫 번째 원인이었다.

2. parent 리스트는 루트 노드를 무조건 보장해주지는 않는다는 것을 잊었다. 다시 한 번 확인하면서 개수를 세어주어야 한 것을 놓친 게 두 번째 원인이었다.

3. 거리를 함수로 만들어서 시간초과가 뜬 것 같다 math의 sqrt를 이용하니까 금방 통과 됐는데 그 이유를 모르겠다. (pypy3 기준)