[백준] 2638(파이썬) - 치즈

https://www.acmicpc.net/problem/2638

2638번: 치즈

• 이 문제는 2636 치즈 문제와 비슷한 문제로, BFS를 이용해서 푸는 문제이다.
• 여기서 조건 중 가장자리의 치즈가 녹는다는 점은 2636번 문제와 비슷하지만 각 치즈 격자의 4 변 중 2 변 이상이 공기와 접촉해야 녹는다는 점을 고려해야 한다.
• 여기서 만약에 치즈가 있을 경우(배열 값이 1일경우) 에는 BFS가 진행되면 안 되므로 q라는 큐 구조에 좌표를 추가하지 않고, 치즈가 없을 경우(0 일 때) BFS가 진행되도록 q라는 구조에 좌표를 추가해준다.
• 2 변 이상이 공기와 접촉할 때 녹게 구현하려면 BFS를 구현해서 2차원 배열 탐색을 실행했을 때 배열 값이 1(치즈일 경우) 일 때 값을 1씩 더해서, 총 2번 더한 값 즉, 3이 되면 녹는다고 가정하면 된다.
• while문을 사용해서 BFS를 실행하고 만약에 없어져야하는칸(2차원 배열 값이 3일 경우) flag를 달아서 하나라도 있으면 flag를 1로 바꿔주고 flag가 1이면 time에 1씩 더해서 시간을 계산해주었다. 만약에 flag가 0이면 녹아야할 치즈가 하나도 없다는 말이기 때문에 while문에서 탈출하도록 구현했다.

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

# def visual (List):
#     for i in range(n):
#         print(List[i])

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

dx = [0,0,1,-1]
dy = [1,-1,0,0]


def bfs():
    q = deque()
    q.append([0,0])
    visited[0][0] = 1
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and visited[nx][ny] == 0:
                if graph[nx][ny] >= 1:
                    graph[nx][ny] += 1
                else:
                    visited[nx][ny] = 1
                    q.append([nx,ny])
time = 0
while 1:
    visited = [[0]*m for _ in range(n)]
    bfs()
    flag = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] >= 3:
                graph[i][j] = 0
                flag = 1
            elif graph[i][j] == 2:
                graph[i][j] = 1
    if flag == 1:
        time += 1
    else:
        break

print(time)

#     if graph[nx][ny] == 0 and visited[nx][ny] == 0:
#         visited[nx][ny] = 1
#         q.append([nx,ny])
#     elif graph[nx][ny] == 1 and (visited[nx][ny] == 1 or visited[nx][ny] == 0):
#         graph[nx][ny] += 1
#         visited[nx][ny] = 1
# elif 0<=nx<n and 0<=ny<m and visited[nx][ny] == 1 and graph[nx][ny] >= 2:
#     cnt += 1
#     graph[nx][ny] = 0
#     visited[nx][ny] = 1