[백준 2638] 치즈 (python)

2638번: 치즈

---

BFS를 통해 해결한다. 외부공기와 치즈 내부의 공간을 구분해야하므로 외부공기를 -1로 바꾼다.

 

1. 시작점을 queue에 담는다.
2. 상하좌우 칸을 확인한다.
3. 만약 0이라면 외부 공기이므로 -1로 바꾸고 queue에 담아준다.
4. 0보다 크다면 치즈이므로 인접한벽을 하나 늘려준다.
5. 만약 인접한벽이 2 이상이라면 nextqueue에 담아준다.
6. 다 돌았다면 queue를 nextqueue로 바꾸어준다.
7. flag를 통해 치즈가 없다면 break한다.

 

import sys
from collections import deque
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

answer = 0
queue = deque([[0, 0]])
while True:
    nextqueue = deque()
    answer += 1
    flag = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] == 0:
                    arr[nx][ny] = -1
                    queue.append([nx, ny])
                elif arr[nx][ny] > 0:
                    flag = False
                    arr[nx][ny] += 1
                    if arr[nx][ny] > 2:
                        nextqueue.append([nx, ny])
                        arr[nx][ny] = -1
    queue = nextqueue
    if flag:
        break

print(answer-1)