[파이썬 PYTHON] 백준 2638번 【치즈】

---

import sys
from collections import deque
import copy

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

queue = deque([])
checked = [[False]*col for _ in range(row)]


dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]


def bfs():
    copiedCheck = copy.deepcopy(checked)
    queue.append([0, 0])
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < row and 0 <= nc < col:
                if _map[nr][nc] == 0 and not copiedCheck[nr][nc]:
                    queue.append([nr, nc])
                    copiedCheck[nr][nc]=True
                elif _map[nr][nc]>0 :
                    _map[nr][nc]+=1

time = 0

while True:

    bfs()
    isRemoved = False
    for r in range(row):
        for c in range(col):
            if _map[r][c]>=3:
                isRemoved = True
                _map[r][c]=0
            elif 0<_map[r][c]<=2:
                _map[r][c]=1
    if isRemoved:
        time+=1
    else:
        break

print(time)

 

문제 접근 방법

1. 치즈가 놓인 모눈종이 가장자리는 무조건 다 0 이고 연결되어 있다. 외부공기라면 (0,0)에서 bfs()를 실행했을때, 예외없이 체킹이 될 것이다.

2. 탐색 중에 공기(0)가 아닌 치즈(1)와 만나는 경우 치즈의 값을 1씩 올린다.

3. 공기에 의해서 2번 이상 치즈의 값이 올라간다면 외부 공기와 2면이 닿아있다는 뜻이다.

4. bfs()가 끝나고 맵 전체를 탐색하면서 치즈 값이 3이상(원래 값이 1인데 2번 이상 터치가 되면 3이상일 것)이라면 0으로 제거한다. 치즈 값이 2 이하라면 다시 1로 만들어준다.

5. 제거된 경우 time에 +1을 하고, 제거된 치즈가 아예 없다면 while문을 탈출한다.