boj 16234人口移転(金貨5)

三星問題
日本
実施中の問題
簡単そうに見えるが、難しいように見えるが、知ったら簡単だと思う.
一度に複数のコンビネーションを生成できることに気づくだけでいい.
私たちは何度もdfsを迂回して、すべての連盟を見つけて、彼らに人口を移転させました.
地図全体を回った後,転機前と人口変化時にカウントする方式で検査を行った.

説明する

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です.
終わりだ!