[백준] 2638: 치즈 python 구현 / BFS

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

 

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

2638번: 치즈

풀이

1. 외부 공기 구분 - (0, 0)은 무조건 외부 공기임
2. 치즈 녹여
3. time 측정

 

CODE

import sys
from collections import deque

n, m = map(int, input().split())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 1. 외부 공기 구분 - (0, 0)은 무조건 외부 공기임
# 외부공기 (9) 내부공기 (0)
def partition_inside(i, j):
    vst1 = [[0]*m for _ in range(n)]
    queue = deque()
    queue.append((i, j))
    paper[i][j] = 9
    vst1[i][j] = 1

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

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx<0 or ny<0 or nx>(n-1) or ny>(m-1): continue
            if vst1[nx][ny] : continue
            
            # 외부 공기일 경우
            if paper[nx][ny] in [0, 9]: 
                paper[nx][ny] = 9
                queue.append((nx, ny))
                vst1[nx][ny] = 1

# 2. 치즈 녹여
def melt_cheese(queue):
    global vst2
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    while queue:
        x, y = queue.popleft()
        dir = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx<0 or ny<0 or nx>(n-1) or ny>(m-1): continue
            if vst2[nx][ny] : continue
            
            # 외부 공기일 경우
            if paper[nx][ny] == 9: 
                dir += 1
            
            # 외부 공기와 두 번 이상 닿으면 녹음 (9)
            if dir == 2:
                paper[x][y] = 9
                vst2[nx][ny] = 0
                break

final_time = 0
split = 1
while 1:
    if split :
        partition_inside(0, 0)
        if all([all(p) for p in paper]): # 외부공기만 있으면 더이상 bfs 중복해서 사용할 필요 x
            split = 0
    
    vst2 = [[0]*m for _ in range(n)]
    queue = deque()
    for i in range(n):
        for j in range(m):
            if paper[i][j] == 1:
                queue.append((i, j))
                vst2[i][j] = 1
    if not queue:
        break
                
    melt_cheese(queue)
    final_time += 1

print(final_time)