백준 구현 대비 인구이동

접근

전체 도시를 순회하면서 각각의 도시를 기준으로 bfs진행후 인구 갱신. 이때 bfs 탐색이 끝난 후 다른 기준 도시를 탐색할때 visited 기록이 있는지 확인해야함. visited기록이 있다면 이미 연합에 속해진적이 있다는 의미므로 연산이 중복된다.

코드

from collections import deque

def bfs(graph,citylist,L,R,N):
  queue=deque(citylist)
  check=False
  movelist=[[0,1],[1,0],[0,-1],[-1,0]]
  visited=[[0 for i in range(N)] for j in range(N)]

  while queue:
    start=queue.popleft()
    if visited[start[0]][start[1]]==1:
      continue
    else:
      visited[start[0]][start[1]]=1
      tempqueue=deque()
      tempqueue.append(start)
      tempcitylist=[]
      totalcity=0
      totalpeople=0
      while tempqueue:
        cur=tempqueue.popleft()
        tempcitylist.append(cur)
        totalcity+=1
        totalpeople+=graph[cur[0]][cur[1]]

        for mo in movelist:
          ni,nj=cur[0]+mo[0],cur[1]+mo[1]
          if 0<=ni<N and 0<=nj<N and L<=abs(graph[cur[0]][cur[1]]-graph[ni][nj])<=R and visited[ni][nj]==0:
            check=True
            tempqueue.append([ni,nj])
            visited[ni][nj]=1
      newpeople=totalpeople//totalcity
      for te in tempcitylist:
        graph[te[0]][te[1]]=newpeople
  

  return check
        

N,L,R=map(int, input().split())

graph=[]

for i in range(N):
  graph.append(list(map(int, input().split())))

citylist=[]
visited=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
  for j in range(N):
    citylist.append([i,j])

day=0
while bfs(graph,citylist,L,R,N):
  day+=1

print(day)

#copy와 새로 선언하는것의 시간 차이