[python] 백준 2638 치즈

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

2638번: 치즈

 

문제 해결

• 전형적으로 그래프 안에서 이동해서 모두 공기가 되는데 까지 걸리는 시간이므로 bfs를 사용하는 것이 좋을 것이다.
• 그런데 문제는 치즈를 중심으로 보는 것이 아니라 공기를 중심으로 언제 녹는 벽(치즈)가 다 없어지는지 확인하는 문제이다.
• 따라서 While 반복문을 통해 시간을 측정하면서 언제 장애물을 안만나는지 확인하면 되는문제
• BFS로 공기를 이동시키면서 어느 치즈지역이 공기를 2번 이상 만나면 치즈를 공기로 바꿔가며 그래프를 모두 공기로 만들면 되는 문제이다.

 

CODE

import sys
input = sys.stdin.readline
from collections import deque

def bfs_air(i,j):
    dxs = [0,0,-1,1]
    dys = [-1,1,0,0]
    que = deque()
    que.append((i,j))
    air[i][j] = 1

    while que:
        x, y = que.popleft()
        for dx, dy in zip(dxs,dys):
            nx = x + dx; ny = y + dy
            if 0<=nx<N and 0<=ny<M:
                if board[nx][ny] ==0 and air[nx][ny] == 0:
                    air[nx][ny] = 1
                    que.append((nx,ny))
                elif board[nx][ny] ==1 :
                    air[nx][ny] += 1
                    if air[nx][ny] >=2:
                        board[nx][ny] = 0




if __name__=='__main__':
    N, M = map(int, input().split()) # 세로, 가로
    board= [list(map(int, input().split())) for _ in range(N)]
    time = 0

    while True:
        air = [[0 for _ in range(M)] for _ in range(N)]
        bfs_air(0,0)
        time += 1
        cnt = 0
        for i in range(N):
            for j in range(M):
                if board[i][j] ==0:
                    cnt += 1
        if cnt== N*M:break
    print(time)