[BOJ 2636] 치즈 (Python)

풀이

처음 BFS 탐색으로 접근하였다. 먼저 치즈를 찾은 후에 치즈의 구멍을 제외한 치즈의 가장자리들의 좌표를 큐에 넣었다. 그리고 큐에서 가장자리들의 좌표들을 꺼내 치즈를 녹였다. 하지만, print()로 찍어보니 이 방법은 잘못된 방법임을 알 수 있었다. 치즈의 구멍도 녹이고 있었다.

문제의 포인트는 치즈부터 찾는 것이 아닌 공기부터 BFS 탐색하는 것이라고 생각한다. 공기인 것만 BFS 탐색을 수행하면서 가장자리의 치즈를 녹이게 되면 치즈의 구멍은 건드리지 않고 가장자리의 치즈만 녹일 수 있게 된다. 간략하게 로직을 설명하겠다.

(1시간 마다 아래 과정이 계속 진행된다고 생각하면 된다!)

1. 판에서 공기인 것을 큐에 넣고 BFS 탐색을 수행한다.

2. 큐에서 공기인 좌표를 하나씩 꺼내면서 4방 탐색을 진행한다.

   • 다음 좌표가 공기이면 다음 좌표를 큐에 넣고 BFS 탐색을 진행
   • 다음 좌표가 치즈라면 치즈를 녹인다. (치즈의 구멍을 건드리지 않게 된다.)
     (--> why?공기인 것부터 찾기 때문에 치즈의 둘러싸인 공기의 좌표는 큐에 들어가지 않게 된다!)

3. 정답 리스트에 치즈의 개수를 삽입한다.

코드

import sys
from collections import deque

input = sys.stdin.readline
row, col = map(int, input().split())
cheese_board = [list(map(int, input().split())) for _ in range(row)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans_list = []


def bfs():
    visited = [[False] * col for _ in range(row)]
    q = deque([(0, 0)])
    visited[0][0] = True
    cheese_cnt = 0  # 1시간 마다 녹는 치즈의 개수 저장

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dir[i][0]
            ny = y + dir[i][1]
            if 0 <= nx < row and 0 <= ny < col and not visited[nx][ny]:
                # 치즈부터 찾는 것이 아닌 공기부터 찾는다.
                # 치즈부터 찾지않고 공기부터 찾게되면 치즈의 구멍은 건드리지 않게 된다.
                if cheese_board[nx][ny] == 0:
                    q.append((nx, ny))
                    visited[nx][ny] = True

                # 가장자리 치즈를 녹인다.
                elif cheese_board[nx][ny] == 1:
                    visited[nx][ny] = True
                    cheese_board[nx][ny] = 0
                    cheese_cnt += 1

    ans_list.append(cheese_cnt)
    return cheese_cnt


while True:
    cnt = bfs()
    if cnt == 0:
        print(len(ans_list) - 1)
        print(ans_list[-2])
        break