[백준] 2638번 치즈 ★

💡문제접근

• 인접한 4변 중에서 적어도 2변 이상이 공기와 접촉한다면 녹아 없어진다는 부분만 추가적으로 구현하여 수월하게 해결할 수 있었다.

💡코드(메모리 : 34192KB, 시간 : 656ms)

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
cheese = [list(map(int, input().strip().split())) for _ in range(N)]

def BFS():
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = 1
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                if cheese[nx][ny] >= 1:
                    cheese[nx][ny] += 1
                else:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))


time = 0
while True:
    visited = [[0 for _ in range(M)] for _ in range(N)]
    BFS()
    flag = 0
    for i in range(N):
        for j in range(M):
            if cheese[i][j] >= 3:
                cheese[i][j] = 0
                flag = 1
            elif cheese[i][j] == 2:
                cheese[i][j] = 1

    if flag == 1:
        time += 1
    else:
        break
print(time)

💡소요시간 : 41m