[백준 2638번] 치즈 (Python3)

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

N,M = map(int,input().split())

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

cheese = []
for i in range(N):
  cheese.append(list(map(int,input().split())))

def melt(n):
  dq = deque()
  dq.append((0,0))
  melted = False
  while dq:
    y,x = dq.popleft()
    if cheese[y][x] == n:
      continue    
    elif cheese[y][x] == -n:
      cheese[y][x] = n
      melted = True
      continue
    elif cheese[y][x] == 1 or cheese[y][x]<0:
      cheese[y][x] = -n
      continue    
    cheese[y][x] = n
    for i in range(4):
      y1 = y+dy[i]
      x1 = x+dx[i]
      if y1>=0 and y1<N and x1>=0 and x1<M:
        if cheese[y1][x1] != n:
          dq.append((y1,x1))
  return melted  

count = 0

while True:
  if melt(count+2):
    count += 1
  else:
    break
  
print(count)

간단한 bfs 문제이다.

0,0에는 치즈가 없으므로 0,0을 외부공기의 시작으로 잡고, 0,0에서부터 BFS를 실행시켜주면 된다.

이때 치즈에 2번 도착하면 녹여주는 방식을 구현하는것이 중요한데, 나는 공기를 순환하면서 n으로 바꿔주고, 한번 녹으면 치즈를 -n으로 바꿔주고, 두번 녹으면 n(공기)으로 바꿔주는 방식으로 구현하였다. 

 

다른 사람들 풀이를 보니 이 문제도 visited 3차원 배열로 푼 경우가 많았다. 나는 bfs에서 visited를 안쓰고 그래프 자체를 직접 바꾸는걸 선호하는 편인데 나중에 한계가 올 수도 있으니 visited를 이용하는 방식도 염두해 두어야겠다.

 

 

오늘의 교훈) 3차원 배열을 염두하자.