[Python] 치즈 - 백준 (BFS)

해당 글은 백준 2638번 '치즈' 문제를 다룬다.

문제

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

2638번: 치즈

 

설명

해당 문제는 치즈의 외부 공간과 내부 공간을 파악하는게 핵심인 문제이다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다는 말을 통해서 (0, 0)부터 탐색하여 외부 공간과 내부 공간을 파악할 수 있다.

본 글에서는 BFS로 해결하였고, 외부 공간을 탐색할 때 치즈가 존재하는 곳이라면 +1을 해준다.(공기가 접촉한 부분)

공기가 접촉한 부분이 기존의 1에서 +2(두 부분)인 3 이상이라면, 1시간 후 치즈가 녹아 없어지는 것이다.

 

코드

from collections import deque
n, m = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

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

def bfs():
    visited = [[False]*m for _ in range(n)]
    q = deque([])
    q.append((0, 0))
    visited[0][0] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < n and ny >= 0 and ny < m:
                if not visited[nx][ny]:
                    if arr[nx][ny] == 0:
                        visited[nx][ny] = True
                        q.append((nx, ny))
                    else:  # 치즈가 존재한다면 공기접촉횟수 +1
                        arr[nx][ny] += 1

result = 0
while True:
    bfs()
    flag = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] >= 3:  # 기존 1에 공기접촉구간 +2 = 3
                arr[i][j] = 0
                flag = 1
            elif arr[i][j] > 1: # 다시 bfs를 위해 초기화
                arr[i][j] = 1
    if flag == 1:
        result += 1
    else:
        break
print(result)