[백준] 2638번 치즈 [Python]

• 문제 : https://www.acmicpc.net/problem/2638
• BFS

from collections import deque

n, m = map(int, input().split())
Map = [list(input().split()) for _ in range(n)]
cnt = 0

for i in range(n): # 치즈 개수 세기
    for j in range(m):
        if Map[i][j] == '1':
            cnt += 1

def bfs():
    Q = deque([[0, 0]])
    visit = [[0] * m for _ in range(n)]
    cheese = [[0] * m for _ in range(n)]

    while Q:
        zx, zy = [0, 0, 1, -1], [1, -1, 0, 0]
        x, y = Q.popleft()

        for i in range(4):
            nx, ny = x+zx[i], y+zy[i]

            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0:
                if Map[nx][ny] == '1':
                    cheese[nx][ny] = cheese[nx][ny] + 1
                else:
                    Q.append([nx, ny])
                    visit[nx][ny] = 1

    return cheese

answer = 0

while cnt != 0: # 치즈 다 녹을 때 까지 bfs반복
    c = bfs()
    answer += 1
    for i in range(n):
        for j in range(m):
            if c[i][j] >= 2:
                cnt -= 1
                Map[i][j] = '0'

print(answer)