[2638] 치즈

문제

https://www.acmicpc.net/problem/2638

풀이

치즈인 부분에서부터 상하좌우를 확인해서 두 면이 치즈가 아닐 경우 지워주는 방식을 생각했었지만 예시 두 번째 그림과 같이 치즈가 아닌 두 면이 접촉했지만 한 쪽 면이 외부 공기가 접촉이 되어있지 않기 때문에 녹지 않는 상황이 존재합니다.

따라서 외부 공기인 위치에서 너비 우선 탐색을 하며 두 번 이상 방문을 한 치즈를 찾아내주고, 지워가며 더 이상 치즈가 존재하지 않을 때까지 반복하며 풀었습니다.

문제에는 맨 가장자리에는 치즈가 놓이지 않는다고 가정 했기 때문에 가장자리는 외부 공기라고 할 수 있고, 가장자리 중 하나인 (0, 0)에서부터 탐색을 해주었습니다.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
result = 0
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))

while True:
    queue = deque([(0, 0)])
    visited = [[False] * M for _ in range(N)]
    remove_list = []
    while queue:  # bfs
        r, c = queue.popleft()
        for move_r, move_c in moves:
            new_r, new_c = r + move_r, c + move_c
            if not 0 <= new_r < N or not 0 <= new_c < M:
                continue

            if board[new_r][new_c] == 1:
                if visited[new_r][new_c]:
                    remove_list.append((new_r, new_c))  # 녹아야하는 치즈
            elif not visited[new_r][new_c]:
                queue.append((new_r, new_c))
            visited[new_r][new_c] = True

    if remove_list: 
        while remove_list:
            r, c = remove_list.pop()
            board[r][c] = 0
    else: # 더 이상 녹는 치즈가 없다면 탐색 종료
        break
    result += 1
print(result)