[Algorithm] BaekJoon : 3055. 脱出byPython

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

📌問題の説明

邪悪な暗黒君主の李民赫はついに魔法の珠を手に入れ、その能力を実験するために近くのティムの森で洪水を起こそうとした.この森にはハリネズミが住んでいる.ハリネズミはできるだけ早く親友のビーバーの巣に逃げて洪水を避けようとした.
ティムの森の地図はR行C列で構成されています.「空いているところは」.水が満ちる地域は「*」、石は「X」と表示されます.ビーバーの穴は「D」で、ハリネズミの位置は「S」と表示されています.
ハリネズミは毎分、現在のグリッドに隣接する4つのグリッドの1つに移動できます.(上、下、右、左)水も毎分空の格子に広がっています.水のある格子に隣接するスペース(少なくとも1つのエッジを共有する)は水になります.水とハリネズミは石を通ることができない.また、ハリネズミは水で満たされたエリアに移動することができず、水もタヌキの巣に移動することができません.
ティムの森の地図を手に入れるときは、ハリネズミがタヌキの巣に安全に移動するのに要する最小時間を求めるプログラムを作成してください.
ハリネズミは予定の水満室に移動できません.つまり、ハリネズミは次の授業で予定の水満の場所に移動できません.移動できるとハリネズミが水に落ちるからだ.
入力
最初の行は、50以下の自然数RおよびCを与える.
「次のR行では、ティダンの森の地図が与えられ、質問で説明した文字だけが与えられます.」D'と'S'は一つだけ
しゅつりょく
1行目の出力ハリネズミはタヌキの穴に移動できる最速時間です.タヌキの巣窟まで安全に移動できない場合は「KAKTUS」を出力します.

💡 問題を解く

問題の指紋は長いですが、整理して「水(*)」と「ハリネズミ(S)」の2種類についてそれぞれBFS検索ができます.
移動順は水の移動がハリネズミの移動より優先なので(→「ハリネズミは次の時間に水がいっぱいになる予定の部屋に移動できません」).
BFS探索は,水,ハリネズミの順で行った.
2つのBFSプローブのために2つのキューが作成された.

queue pet:ハリネズミ

列water:水

水は移動をチェックするだけで済むので(行,列)資料は行列に入れ,ハリネズミはタヌキ洞(D)の最短時間(移動時間,行,列)資料を求めて行列に入れる.
ハリネズミを動かす場合、移動後の位置は「S」、移動前の位置は「.」を行うように変更します.
目的地(D)に到達した場合、正解を出力する「解答」変数に最小時間値を加え、ナビゲーションを完了する.
コードは次のとおりです.

import sys
from collections import deque

d = [(-1, 0), (1, 0), (0, 1), (0, -1)]
R, C = map(int, input().split())
maps = [list(' '.join(map(str, sys.stdin.readline().split()))) for _ in range(R)]

def move_water():
    global R, C
    for _ in range(len(queue_water)):
        r, c = queue_water.popleft()
        for idx in range(4):
            nr = r + d[idx][0]
            nc = c + d[idx][1]
            if 0 <= nr < R and 0 <= nc < C:
                if maps[nr][nc] == '.':
                    maps[nr][nc] = '*'
                    queue_water.append((nr, nc))
                    visited[nr][nc] = 1

def move_pet(cnt):
    global answer
    for _ in range(len(queue_pet)):
        m, r, c = queue_pet.popleft()
        for idx in range(4):
            nr = r + d[idx][0]
            nc = c + d[idx][1]
            if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc]:
                if maps[nr][nc] == '.':
                    queue_pet.append((cnt+1, nr, nc))
                    maps[nr][nc], maps[r][c] = 'S', '.'
                    visited[nr][nc] = 1
                if maps[nr][nc] == 'D':
                    answer = cnt+1

queue_pet = deque([])
queue_water = deque([])
visited = [[0] * C for _ in range(R)]
for r in range(R):
    for c in range(C):
        if maps[r][c] == 'S':
            queue_pet.append((0, r, c))
            visited[r][c] = 1
        if maps[r][c] == '*':
            queue_water.append((r, c))
            visited[r][c] = 1

answer = 'KAKTUS'
cnt = 0
while queue_pet: # 고슴도치가 이동이 가능할 때 까지 BFS 탐색
    move_water() # 1. 물 BFS
    move_pet(cnt) # 2. 고슴도치 BFS
    cnt += 1
    if answer != 'KAKTUS': break # answer값이 최소시간으로 변경되면 탐색을 마친다.
print(answer)