백준 #2636 치즈

문제 링크

[2636 치즈]

문제 설명

판의 가장자리에서 공기가 유입된다. 치즈는 공기에 닿으면 1시간 후에 녹게되고 치즈가 전부 녹게 되는 시간을 구하는 문제

코드

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


def bfs():
    q = deque()
    q.append((0, 0))
    visited = [[False] * M for _ in range(N)]
    visited[0][0] = True
    cnt = 0
    while q:
        r, c = q.popleft()
        for k in range(4):
            nr, nc = r + dr[k], c + dc[k]
            if nr < 0 or nr >= N or nc < 0 or nc >= M:
                continue
            if visited[nr][nc]:
                continue
            if arr[nr][nc] == 1:
                arr[nr][nc] = 0
                cnt += 1
                visited[nr][nc] = True
            else:
                visited[nr][nc] = True
                q.append((nr, nc))

    return cnt


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
time = 0
last = 0
while True:
    cnt = bfs()
    if cnt == 0:
        print(time)
        print(last)
        break
    time += 1
    last = cnt

풀이

공기가 밖에서 유입되기때문에 바깥부터 치즈를 녹여주어야한다. 처음에 큐에다가 치즈를 모두 넣어놓고 4방향을 확인해서 공기에 닿는 치즈는 녹이는 방법으로 하려고 했었는데 틀린 생각이였다. 중요한건 공기가 바깥에서부터 오기 때문에 치즈 안에 구멍이 뚫려있고 거기에 치즈가 있다해도 안에있는 치즈는 바깥의 치즈에 가로막혀 녹지 못한다. 치즈가 다 녹을때까지 BFS를 반복해주면서 시간과 녹인 치즈의 개수를 체크해주었다!