1 minute read

문제

접근 방법

바깥 공기(0)에 닿아있는 치즈들(1)을 한번에 다 확인하고 없애는 과정을 반복해야 문제를 풀 수 있음을 알 수 있다. 공기에 닿아있는 치즈를 확인하기 위해서 가장자리에서 bfs를 시작하여 0으로만 이동하면서 1을 발견할 때, 그 1의 좌표들을 저장하였다. 이 좌표들에 들어있는 치즈(1)은 1초가 지나면 녹기 때문에 0으로 바꾸고 다시 bfs를 반복하였다.

세로, 가로 길이가 최대 100이기 때문에 bfs를 100x100번 돌려야 시간 초과가 난다는 것을 통해 편하게 bfs를 반복하였다.

정답 코드


import sys
from collections import deque

input = sys.stdin.readline
"""

0,0에서 0에서만 움직이면서 bfs를 하여 1을 발견하면, 그 치즈는 이제 없어질 치즈이기에 이 좌표들을 저장하여 bfs가 끝나면 0으로 바꿈

이 과정을 발견한 치즈가 없을 때까지 반복

이 과정을 반복한 횟수가 답이다.

"""

n,m = map(int,input().split())

maps = []
for _ in range(n):
  maps.append(list(map(int, input().split())))

moves = [(0,1), (0,-1), (1,0), (-1,0)]

def bfs():
  q = deque([(0,0)])
  visited = [[False]*(m) for _ in range(n)]
  visited[0][0] = True

  melts = [] #녹은 치즈들의 좌표 저장
  while q:
    h,w = q.popleft()
    for dh, dw in moves:
      new_h, new_w = h+dh, w+dw
      if 0<=new_h<n and 0<=new_w<m and not visited[new_h][new_w]:
        #치즈 아니라면
        if maps[new_h][new_w]==0:
          visited[new_h][new_w] = True
          q.append((new_h, new_w)) #0으로만 이동
        #치즈라면
        else:
          visited[new_h][new_w] = True
          melts.append((new_h, new_w)) #녹을 치즈 저장

  return melts

time = 0
befores = [] #이전 시간들에서 녹은 치즈의 개수들을 저장
while True:
  melts = bfs()
  if melts:
    time+=1

    before=0
    for h,w in melts:
      maps[h][w] = 0
      before += 1

    befores.append(before)

  else:
    break

print(time)
print(befores.pop())

You May Also Enjoy