[백준] 치즈 - python (2638번)

전체적인 풀이 방향

1. 항상 (0, 0)부터 보면서 외부 공기를 탐색합니다.

모눈종이를 (0,0)부터 탐색하며 맞닿아있는 공기, 즉 외부공기들을 모두 0 -> 2로 바꾸어준다. 이때 모눈종이를 복사하여 바꿔줘야 합니당.

2. 외부공기를 복사한 모눈종이에 2로 바꿔준 뒤 원본 모눈종이에서 치즈들을 탐색하면서 2면 이상이 외부공기와 맞닿아있는 치즈를 0으로 바꿔줍니다.

원본 모눈종이에 남아있는 치즈들을 탐색하며 모눈종이 복사본에 체크한 외부공기와 2면 이상 맞닿아있는 치즈들은 원본 모눈종이에서 0으로 바꿔줍니다. 원본 모눈종이에서 바꾸는 이유는 다음 번 (0,0)부터 탐색할 때 치즈를 없앤 상태에서 같은 탐색을 반복해야 하기 때문입니다.

3. 1, 2번을 반복합니당

import sys
from collections import deque
from copy import deepcopy

input = sys.stdin.readline

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


def bound(x, y):
    return 0 <= x < N and 0 <= y < M

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

visited = [[0] * M  for _ in range(N)]

answer = 0

def bfs():
    board2 = deepcopy(board)
    rot = 0
    q = deque()
    q.append((0, 0))
    board2[0][0] = 2
    visited[0][0] = 1
    # 1. 우선 외부공기 2로 바꾸기
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if bound(nx, ny):
                if board2[nx][ny] == 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    board2[nx][ny] = 2
                    q.append((nx, ny))

    # 2. 치즈들 보면서 외부공기와 2면 이상 접하면 0으로 만들기
    for i in range(N):
        for j in range(M):
            if board[i][j] == 1:
                cnt = 0
                for d in range(4):
                    nx = i + dx[d]
                    ny = j + dy[d]
                    if bound(nx, ny):
                        if board2[nx][ny] == 2:
                            cnt += 1
                if cnt >= 2:
                    board[i][j] = 0
                    rot = 1
                
    return rot


while True:
    visited = [[0] * M for _ in range(N)]
    rot = bfs()
    if rot == 0:  # 더 이상 남아있는 치즈가 없다는 뜻
        break
    else:
        answer += 1

print(answer)