[Algorithm] BaekJoon : 2636. チーズby Python

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

📌問題の説明

下図1に示すように、正方形の格子からなる正方形の板があり、その上に薄いチーズ(灰色の部分)が置かれています.板の縁(<図1>では、四角形のXの部分)にはチーズが入っておらず、チーズには1つ以上の穴が開いていてもよい.
これらのチーズを空気中に入れると溶け、空気に触れる車両は1時間後に溶けます.チーズの穴には空気が入っていませんが、穴を囲むチーズが溶けて穴が開くと空気が穴に入ります.<図1>に示すように、チーズ孔を囲むチーズは溶けず、図2>に示すように、「c」と表記された部分だけが1時間後に溶けて消える.

あと1時間で<図2>の「c」で表される部分は<図3>に示すように溶けて消えてしまいます.

<図3>チーズが2時間後の様子で、残りの破片はあと1時間で全部溶けてしまいました.そのため、初めてチーズが全部溶けて消えるまで3時間かかります.<図3>に示すように、チーズは融解中にいくつかに分けることができる.
矩形板の大きさとチーズが板に置かれたとき、空気中のチーズがすべて溶けるのに要する時間と、すべて溶ける1時間前にチーズの破片が残った格子数を入力するプログラムを作成します.
入力
最初の行は、矩形板の縦横長が正の整数であることを示します.縦横の長さは最大100です.板上の各横線の形状は、上から下へ順に2行目から最後の行までです.チーズのない格子は0で、チーズのある格子は1で、数字の間にスペースがあります.
しゅつりょく
1行目はチーズが全部溶けて消えるまでの時間を出力し、2行目は全部溶ける1時間前に置いたチーズの破片の格子数を出力します.

💡 問題を解く

DFS/BFSの実装(シミュレーション)問題の適用
板の縁にはいつもチーズがないので(0,0)から探索します.
DFS/BFSは、すべてのチーズが溶けるまで実行します.
時間+1を実行するごとに、所要時間を求める.
また、残りのチーズスライスの数を1時間前に求める必要があるため、実行するたびに変数(last)でチーズスライスの数を更新する.
コードは次のとおりです.

import sys
from collections import deque

R, C = map(int, input().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(R)]

cheese = 0
for row in maps: # 치즈조각이 놓여있는 칸의 총 개수
    cheese += sum(row)
last = cheese # 한 시간 전 치즈의 개수를 담을 변수

d = [(-1, 0), (1, 0), (0, 1), (0, -1)]
def bfs(): # BFS
    global cheese
    visited = [[0] * C for _ in range(R)]
    queue = deque([(0, 0)])
    visited[0][0] = 1
    while queue:
        r, c = queue.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]:
                    maps[nr][nc] = 0
                    cheese -= 1
                else:
                    queue.append((nr, nc))
                visited[nr][nc] = 1
time = 0
while cheese: # 치즈가 녹을 때 까지 BFS 실행
    bfs()
    if cheese: last = cheese # 다 녹기 전 치즈개수 업데이트(= 1시간 전)
    time += 1 # 시간+1
print(time)
print(last)