[백준/dfs] 10216번: Count Circle Groups

-문제: https://www.acmicpc.net/problem/10216

처음에는 bfs로 진행했고, 1) 적군 지역을 모두 visit리스트에 입력한 뒤, 2) 하나의 적군지역을 기준으로 주어진 범위에 해당하는(r만큼) 통신지역을 모두 q에 넣는다. 

3) 다음 적군으로 이동했을 때(visit에서 popleft()) 해당 적군의 통신 지역이 q에 있다면 통신 지역이 겹치는 것이므로 cnt의 값을 하나씩 지워나가는 방식으로 갯수를 구하려고 했는데 시간초과가 발생해서 다른 방법을 찾아보았다.

참고한 블로그

-정답풀이: 

dfs() 식 풀이

1-1) distance(location[current],location[j]):

current번째 적군과 어떤 적군 사이의 거리

1-2) (location[current][2]+location[j][2]):

location[current][2]: current 적군의 통신 범위(반지름 길이)

location[j][2]: 어떤 적군의 통신 범위(반지름 길이)

2) cur==j:

자기 자신에 대해서 연산을 수행하는 경우

3) visit[j]:

이미 방문한 적군

 

===>위의 3가지 경우(통신 범위가 다른 적군의 통신 범위에 미치지 못하는 경우, 자기 자신인 경우, 이미 방문한 적군인 경우)에는 continue를 하고, 이 외의 상황에 대해서 방문 처리를 하고, 재귀를 수행한다 

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

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

 

-시간초과 풀이:

처음에 a,b,c in visit: 라고 실행했었는데, 이렇게 하니 Error가 발생해서 파이썬 튜터로 정확히 어떤 문제인지 찾아보니 

deque mutated during iteration 에러였다. 이거는 deque가 반복문을 돌리 때 deque의 내용이 변질되거나 사이즈가 변경될 때 뜨는 오류라고해서 visit를 deep copy한 result를 설정해서 돌려주었다. 그러더니 시간초과가 발생했다. 

from collections import deque
import copy
def bfs(x,y,r):
    global cnt
    flag=False
    q=deque()
    while visit:
        x,y,r=visit.popleft()
        for i in range(4):
            for j in range(1,r+1):
                a,b=x+j*dx[i],y+j*dy[i]
                if (a,b) not in q:
                    q.append((a,b))
                else:
                    flag=True
                    continue
        if flag:
            cnt-=1 #겹치는 구역 하나씩 빼기
            
t=int(input())
dx=[-1,1,0,0]
dy=[0,0,-1,1]
for _ in range(t):
    n=int(input())
    visit=deque()
    for _ in range(n):
        x,y,r=map(int,input().split())
        visit.append((x,y,r))
    result=copy.deepcopy(visit)    
    cnt=n
    for a,b,c in result:
        bfs(a,b,c)
    cnt=n
    print(cnt)