치즈 [백준 2638]
https://www.acmicpc.net/problem/2638
외부 공기에 닿은 치즈는 1시간 뒤에 녹는다. 이때 치즈가 전부 녹는 시간을 구하여라
처음에는 내부에 있는 공간의 좌표를 모두 조사해서 공기라도 내부에 있으면 외부로 생각 안하게끔 하려고 했는데 쉽지 않았다. 근데 생각해보니 bfs 를 사용하여 공기인 곳을 찾아 0, 0 에서부터 조사하면 내부로 갈 일이 없어보였다. 해서 닿은 면적이 2면 이상이면 녹이는 코드를 작성할 수 있었다.
from collections import deque
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def melt():
q = deque()
q.append((0, 0))
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 not visited[nx][ny]:
if board[nx][ny] >= 1:
board[nx][ny] += 1
else:
visited[nx][ny] = True
q.append((nx, ny))
cnt_cheeze = 0
for i in range(n):
for j in range(m):
if board[i][j] == 1:
cnt_cheeze += 1
time = 0
while True:
if cnt_cheeze == 0:
break
visited = [[False] * m for _ in range(n)]
melt()
cnt = 0
for i in range(n):
for j in range(m):
if board[i][j] >= 3:
board[i][j] = 0
cnt += 1
elif 1 <= board[i][j] < 3:
board[i][j] = 1
cnt_cheeze -= cnt
time += 1
print(time)