[BOJ] 백준 2638번 문제 풀이 (Python)

1. 문제 풀이

치즈의 외부 공간과 내부 공간을 구분해서 치즈가 언제 녹아없어지는지 확인해야하기 때문에 BFS를 여러번 사용해야하는 문제였다.

• 치즈가 있는 공간을 구분할 필요가 없다면 BFS를 1번만 사용해서 풀 수 있다.

반복문을 사용해 시간을 측정한다. BFS를 사용해서 치즈가 완전히 녹는지 확인하고 모든 치즈가 녹으면 반복문을 종료한 뒤 시간을 출력한다.

2. 코드

import sys
from collections import deque
from itertools import chain
def input(): return sys.stdin.readline().rstrip()

def bfs():
    empty = [(0,0), (0,m-1), (n-1,0), (n-1,m-1)]
    visited = [[0]* m for _ in range(n)]
    q = deque(empty)
    cnt = 0
    for y, x in empty:
        visited[y][x] = 1
    while q:
        y, x = q.popleft()
        for idx in range(4):
            dy, dx = y + my[idx], x + mx[idx]
            if dy <0 or dy >= n or dx <0 or dx >= m: continue
            if matrix[dy][dx]:
                visited[dy][dx] += 1
                if visited[dy][dx] == 2:
                    matrix[dy][dx] = 0
                    cnt += 1
            if not visited[dy][dx]:
                visited[dy][dx] = 1
                q.append((dy,dx))
    return cnt

def time_count():
    cheeze_cnt = sum(chain(*matrix))
    t = 0
    while cheeze_cnt > 0:
        cheeze_cnt -= bfs()
        t += 1
    return t

n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
my = [1,-1,0,0]
mx = [0,0,1,-1]

print(time_count())