[Algorithm] BaekJoon : 19237. 大人のサメbyPython

[問題のショートカット]https://www.acmicpc.net/problem/19237

📌問題の説明

青少年サメはさらに大人のサメになった.サメが住んでいる空間には魚がいなくなり、他のサメしか残っていません.サメには1以上M以下の自然数の番号があり、それぞれの番号が異なります.サメたちは領地を死守するため、他のサメを追い払おうとしたが、1番の大きなサメが一番強く、残りの全員を追い払うことができた.
N×Nサイズの格子の中、M個の格子の中にサメが1匹いました.最初は、すべてのサメが自分の位置で自分のにおいを放っていました.その後1秒ごとに、すべてのサメが上下左右に隣接する格子の一つに同時に移動し、自分のにおいを格子にこぼした.サメはk回移動するとにおいが消えます.
各サメが移動方向を決定すると、まず隣接する格子ににおいのない格子の方向をつかむ.そのような格子がなければ、自分のにおいのする格子の方向につかむ.この場合、複数のセルがある可能性があります.この場合、特定の優先度に従います.優先順位はサメによって異なり、同じサメでも今見ている方向によって異なります.サメが最初に見た方向は入力で、それから移動したばかりの方向です.
すべてのサメが移動すると、1つの格子に複数のサメがいる場合、番号が一番小さいサメを除いて、すべてのサメが格子から追い出されます.


<図1>最初はすべてのサメが自分のにおいを放つ状態を示し、<表1>は各サメと現在の方向による優先度を示した.この例では、k=4である.左下隅に書かれた整数はにおいを表し、その値は消えた残りの時間である.左上に書かれた整数は、サメの番号やにおいを放つサメの番号を意味します.


<図2>はすべてのサメが1マス移動して自分のにおいを放つ状態であり、<図3>は<図2>の状態でさらに1マス移動する.(2,4)サメ2と4が一緒に到着したため、サメ4はメッシュから追い出された.


<図4>メッシュに残っているすべてのサメが1マス移動して自分のにおいを放つことを示し、<図5>は<図4>でまた1マス移動したことを示す.サメ2は隣接する格子に何のにおいもしないので、自分のにおいがする(2,4)まで移動した.サメが移動すると、最初に各サメが放つにおいが消えた.
この手順を繰り返す場合は、1番のサメだけがグリッドに残るのに数秒かかる時間を求めるプログラムを作成してください.
入力
1行目はN MK(2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)
次の行からN行にメッシュが表示されます.0はスペース、0はxはサメを含むスペースを表します.
次の行は各サメの方向を順番に示します.1,2,3,4はそれぞれ上、下、左、右を表す.
次の行から、サメ1匹あたりの方向優先順位はサメ1匹あたり4行です.各行は4つの数で構成されています.1本のサメを表す4行のうち、1行目はそのサメが上向きの方向優先度、2行目は下向きの優先度、3行目は左向きの優先度、4行目は右向きの優先度である.各優先度に1～4の自然数が表示されます.一番先に出る方向が最優先です.たとえば、優先度が1 3 2 4の場合、方向は上、左、下、右の順になります.
最初は、サメごとに隣接するスペースがありました.そのため、最初から移動できない場合はありません.
しゅつりょく
出力はサメ1号だけがグリッドに残るのに要する時間です.しかし、1000秒を超えても他のサメがグリッドに残っている場合は、−1が出力される.

💡 問題を解く

「サメシリーズのターミネーター(?)」「大きなサメ」問題は、問題の内容を順番に表す「シミュレーション」タイプの問題です.
複雑そうに見えますが、問題の順序を正しく理解すれば、簡単に解決できます.
step 1)
変数の設定

d:サメ移動配列(上、下、左、右)

tank:NxN(サメ移動アレイ)

サメd:サメの優先方向を示すディクバンナリー

n d(now direction):現在のサメの方向を含む配列

生存:サメが生存するかどうか

時間:かかる時間

step 2)
問題を解決するためにサメの活動を段階的に行います.

の隣接する格子の中で移動可能な格子を探す.(優先)→find関数

1号で見つけた格子で、サメたちがそれぞれ移動している間に、自分より小さいサメに遭遇すると、番号の大きいサメが追い払われます.そうでなければ、自分のにおいを格子にこぼします.→move関数

移動後、サメが残した味の時間はすべて-1です.→delete関数

step 3)
find関数を使用して、次の移動するセルを検索します.
1番からM番まで並んでいるサメについて、次の移動する格子を探します.

ready:1番からM番サメの次の移動欄までの情報配列.
※readyには(サメの番号、移動する行座標、移動する列座標、方向)の値が含まれています.

優先順位を考慮して、移動するセルを探すときは、移動可能なセルがない場合は、経過したセルに戻る必要があります.→同じように自分が通ったチェック情報を含めます.
複数の移動可能なセルがある場合は、最も優先度の高いセルに移動します.→できるだけ最初のメッセージをreadyに入れる.

可能:隣接するセルに移動可能なセルを含む配列

step 4)
move関数を使用してサメを移動します.
readyには1番からM番までの昇順でサメの移動情報が含まれています.
そのため、移動中に大きなサメと小さなサメが同じ格子で出会うと、大きなサメを追い払うことになります.
また、move関数の後にdelete関数でにおいを表示する時間(?)乙-1を作るので、初めての味の値はk+1です.
step 5)
delete関数を使用して、サメが領域を通過するにおい時間を-1に短縮します.
においの時間が1より大きい場合は−1、1であれば[0,0]の値を与えて痕跡を消す.
コードは次のとおりです.

import sys

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def find(s):
    for r in range(N):
        for c in range(N):
            if tank[r][c][0] == s and tank[r][c][1] == k:
                turn = sharks_d[s][n_d[s]-1]
                same = ''
                possible = []
                for t in turn:
                    nr = r + d[t-1][0]
                    nc = c + d[t-1][1]
                    if 0 <= nr < N and 0 <= nc < N:
                        if tank[nr][nc][0] == 0:
                            possible.append((s, nr, nc, t))
                        elif tank[nr][nc][0] == s and not same:
                            same = (s, nr, nc, t)
                if len(possible):
                    ready.append(possible[0])
                else:
                    ready.append(same)
                return

def delete():
    global N
    for r in range(N):
        for c in range(N):
            if tank[r][c][0]:
                if tank[r][c][1] == 1:
                    tank[r][c] = [0, 0]
                else:
                    tank[r][c][1] -= 1

def move(ready):
    for r in ready:
        if tank[r[1]][r[2]][0] and tank[r[1]][r[2]][0] < r[0]:
            survive[r[0]] = 0
            continue
        tank[r[1]][r[2]] = [r[0], k+1]
        n_d[r[0]] = r[3]

N, M, k = map(int, input().split())

tank = [[[0, 0] for _ in range(N)] for _ in range(N)]

for r in range(N):
    temp = list(map(int, input().split()))
    for c in range(len(temp)):
        if temp[c]:
            tank[r][c] = [temp[c], k]

n_d = [0] + list(map(int, input().split())) # 상어 현재 방향

sharks_d = {} # 상어 우선순위 방향
for m in range(M):
    before = [list(map(int, sys.stdin.readline().split())) for _ in range(4)]
    sharks_d[m+1] = before


survive = [0] + [1] * (M) # 상어 생존 여부
time = 0 # 걸린 시간

while True:
    ready = []
    for s in range(1, 1+M):
        if survive[s]:
            find(s)
    move(ready)
    delete()

    time += 1
    if sum(survive) == 1:
        break
    if time > 1000:
        break

print(-1 if time > 1000 else time)

サメが同時に動いているので、同じ格子で衝突する場合...
最初は1番からそのまま入れていたのですが、結果的に次の番号では移動できない格子と思われ、欲しくない結果が得られました.
同時にすべてのオブジェクト(?)移動中に競合が発生した場合は、すべての候補者を選択して比較します.