boj 16234 인구이동 (골드5)

삼성문제이다

boj 16234 인구이동

역시나 구현구현한 문제

쉬운듯 하면서도 어려운듯 하면서도 알고나면 쉬운?
연합이 한번에 여러개 생길수 있다는점만 주의하면 될것같다.
dfs를 여러번 돌리면서 연합들을 모두 찾아 인구이동을 시켜주고
전체 맵을 다 돌았을때 돌기전이랑 인구변화가 생겼으면 count 해주는 방식으로 체크했다.

내 풀이

from collections import deque
import copy
n,l,r = map(int,input().split())

back = [list(map(int,input().split())) for _ in range(n) ]

visit = [[False] * n for _ in range(n) ]

num = 0 
y , x = [0,1,0,-1], [1,0,-1,0]

def dfs(p,q):
  global back
  count = 0
  queue = deque()
  queue.append((p,q))
  temp = []

  while(queue):
    i,j = queue.pop()

    for k in range(4):
      ny = i + y[k]
      nx = j + x[k]

      if ny < 0 or ny >=n or nx <0 or nx >=n or visit[ny][nx] == True :
        continue

      if  l <= abs(back[ny][nx] - back[i][j]) <= r:
        visit[ny][nx] = True
        queue.append((ny,nx))
        temp.append((ny,nx))
        count += back[ny][nx]

  if len(temp) != 0:
    count = count// len(temp)
    for ty,tx in temp:
      back[ty][tx] = count

answer = 0

while(1):
  tempback = copy.deepcopy(back)

  for i in range(n):
    for j in range(n):
      if visit[i][j] == False:
        dfs(i,j)

  if tempback == back:
    break

  visit = [[False] * n for _ in range(n) ]
  answer += 1


print(answer)

결과

주의점

  for i in range(n):
    for j in range(n):
      if visit[i][j] == False:
        dfs(i,j)

이 부분에서 if visit == false 조건을 안 넣어줘서 한참 시간을 썼다.
안넣어도 어차피 내부에서 한번 검토를 하니깐 상관없을거라 생각했는데
방문했던곳이 일단 큐에 들어가게 되면 거기서 탐색을 시작해서 방문 안한노드로 만약 탐색이 진행될경우 인구이동을 나중에 한번에 시켜준다면 문제가 없겠지만 주어진 풀이에서는 미리 시켜주었기 때문에 주어진 맵과 다른 형태의 연합이 형성될 수 있어서 꼭 넣어줘야 한다!
짜놓은 코드에서는 현재 노드가 방문했던곳인지는 체크를 안하고 그 노드로부터 탐색가능한 다음 노드들이 방문했던곳인지만 체크하고있어서 문제가 발생한것!

안되는 이유를 못찾고, 혹시나 해서 넣었다가 이부분 추가하니깐 되길래 왜 이게 추가되어야할까 고민하다가
안떠올라서 그냥 잤는데 자고일어나니깐 머릿속에 쫙 상황이 떠오른다

아 그리고 pypy가 아닌 python에서는 시간초과가 난다..
혹시 dfs나 bfs나 뭐가 더 빠를까 체크해봤는데 똑같은것같다
위 결과 사진에서 1개는 dfs, 1개는 bfs이다

끝!