[python] 백준 2636 치즈

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

2636번: 치즈

 

문제 해결

• 시간에 따라 치즈가 녹아서 없어지는 문제 → 시뮬레이션
• 가장자리는 치즈가 놓이지 않는다는 가정이 있으므로 그 중 하나인 (0,0)은 치즈가 없다.
• 치즈 안에 닫혀있는 공기는 상관x
• 따라서 치즈 밖에 있는 공기로 계속 퍼져나가고 치즈를 만나면 치즈를 녹인다.(그리고 더이상 그 지역에선 이동하지 않는다.) -> 이는 BFS를 통해 구현할 수 있다.
• 한 타임에 녹는 치즈의 개수를 세서 리스트에 저장한다.

 

CODE

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

def bfs():
    que = deque()
    que.append([0,0])
    visited[0][0] = 1
    cnt = 0
    while que:
        x, y = que.popleft()
        for dx, dy in zip(dxs, dys):
            new_x = x + dx
            new_y = y + dy
            if 0<=new_x<r and 0<=new_y<c and visited[new_x][new_y] == 0:
                if graph[new_x][new_y] ==0:
                    visited[new_x][new_y] = 1
                    que.append([new_x,new_y])
                elif graph[new_x][new_y] == 1:
                    graph[new_x][new_y] = 0
                    visited[new_x][new_y] = 1
                    cnt += 1
    ans.append(cnt)
    return cnt

def simulate():
    time = 0
    while 1:
        time += 1
        for i in range(r):
            for j in range(c):
                visited[i][j] = 0
        cnt = bfs()
        if cnt ==0: break
    print(time-1)
    print(ans[-2])

if __name__=='__main__':
    r, c = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(r)]
    dxs = [1,-1,0,0]
    dys = [0,0,1,-1]
    ans = []
    visited = [[0]*c for _ in range(r)]
    simulate()