이번 문제는 깊이우선탐색을 통해 해결하였다. 처음에는 5000*5000의 그래프를 생성하여 범위에 해당하는 위치를 모두 체크하여 연결되는 범위의 수를 세는 방식으로 해결하려고 하였다. 그러나 인덱스 에러와 시간초과에 시달리는 결과가 도출됐다...

그래서 다른 방향으로 생각해보기로 했다. 각 좌표와 반지름을 담은 2차원 리스트를 하나씩 순회하면서 다른 좌표와의 거리와 반지름 합을 비교하여 겹칠 경우 그 좌표를 방문처리하여 같은 영역으로 간주하는 방식으로 접근하였다. 코드는 길지 않았지만 입력 값의 범위 때문인지 시간초과가 다시 발생하였고, 파이썬에 비해 빠른 PyPy3로 제출하여 성공하였다.

• 거리를 구하는 함수 distance를 a, b를 인자로 갖도록 선언한다.
  -> a[0]-b[0]의 제곱 + a[1]-b[1]의 제곱을 반환한다.
• dfs함수를 cur을 인자로 갖도록 선언한다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 distance(location[cur], location[j])가 location[cur][2]+location[j][2]의 제곱보다 크거나, cur이 j와 같거나, visited[j]가 True인 경우에는 다음 반복을 진행한다.
  --> visited[j]를 True로 갱신한다.
  --> dfs(j)를 재귀호출한다.
• t를 입력받는다.
• t번 반복하는 for문을 돌린다.
  -> n을 입력받는다.
  -> 정답을 저장할 변수 answer를 0으로 선언한다.
  -> 좌표와 반지름을 저장할 리스트 location을 선언한다.
  -> 방문처리 리스트 visited를 n개의 False로 채운다.
  -> n번 반복하는 for문을 돌린다.
  --> location을 입력받는다.
  -> n번 반복하는 for문을 돌린다.
  --> visited[i]가 False일 경우,
  ---> dfs(i)를 호출한다.
  ---> answer를 1 증가시킨다.
  -> answer를 출력한다.

Code

import sys
input = sys.stdin.readline
def distance(a, b):
    return (a[0]-b[0])**2+(a[1]-b[1])**2

def dfs(cur):
    for j in range(n):
        if distance(location[cur], location[j])>(location[cur][2]+location[j][2])**2 or cur==j or visited[j]:
            continue
        visited[j]=True
        dfs(j)
t=int(input())
for _ in range(t):
    n=int(input())
    answer=0
    location=[]
    visited=[False for _ in range(n)]
    for _ in range(n):
        location.append(list(map(int, input().split())))
    for i in range(n):
        if not visited[i]:
            dfs(i)
            answer+=1
    print(answer)