[백준] 치즈

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

2638번: 치즈

BFS를 활용한 문제입니다. 가장자리(0,0)부터 BFS를 통해 사방탐색을 진행하면서 다음이 빈 공간이면 큐에 넣어주고 치즈이면 공기와 맞닿아있는 치즈이므로 cnt를 늘려준 다음 2이상인 치즈는 제거해주면 됩니다.

 

import sys
from collections import deque
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline


n, m = tuple(map(int, input().split()))

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


dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]

t = 0

def inRange(y, x):
    return 0 <= y < n and 0 <= x < m


def bfs():
    visited = [
        [False] * m
        for _ in range(n)
    ]

    cnt = [
        [0] * m
        for _ in range(n)
    ]

    visited[0][0] = True

    q = deque([(0, 0)])

    while q:
        y, x = q.popleft()

        for dy, dx in zip(dys, dxs):
            ny = y + dy
            nx = x + dx
            if inRange(ny, nx) and not visited[ny][nx]:
                # 다음이 치즈이면 실내 공기와 접촉했으므로 1증가
                if board[ny][nx] == 1:
                    cnt[ny][nx] += 1
                else:
                    visited[ny][nx] = True
                    q.append((ny, nx))

    isExist = 0
    for i in range(n):
        for j in range(m):
            if board[i][j]:
                isExist += 1

            if cnt[i][j] >= 2:
                board[i][j] = 0

    return False if isExist == 0 else True




while bfs():
    t += 1

print(t)