[백준/2636/파이썬] 치즈

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

2636번: 치즈

Problem

• 아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 
• 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.
• 입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

조건

• 치즈 속의 공기에서는 치즈가 녹지 않는다. ( 치즈내부의 공기 때문에 녹는 상황은 없다. )
• 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.
• 첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

SOL

무려 올림피아드 "초등부" 문제이다. 정말 무섭다 . 이 문제는 생각 해볼게 있는 문제이다.

공기에 닿아서 녹는 유형의 시뮬레이션 문제는 주로, 치즈 / 빙산/ 섬이 지구온난화로 인해서 가라앉고 있다던지 등등이 있을 수 있다.

 

여기서, "0"(공기)를 기준으로 주변이 "0"(공기)이면 deque에 넣고 방문처리를 해준다. 그후, bfs를 진행해주고, "1"(치즈)를 만난다면, 녹여주고, 방문처리를 해주고, deque에 넣지 않는다.

 

이렇게 된다면, 0,0부터 순차적으로, 공기를 체크해주고, 공기에 처음으로 맞닿는 치즈는 녹여주게 된다.

그리고, 방문처리를 해주었기 때문에, 치즈 속의 공기까지 들어갈 일이 없다.

 

#cheese 

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

N,M =map(int,input().split())
cheese=[list(map(int,input().split())) for _ in range(N)]
dx=[0,1,-1,0]
dy=[1,0,0,-1]

def bfs():
    dq=deque()
    dq.append((0,0))
    visited=[[0 for _ in range(M)] for _ in range(N)]
    visited[0][0] = 1
    Last_piece=0
    while dq:
        y,x= dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not (0<=ny<N and 0<=nx<M):
                continue
            if cheese[ny][nx] ==0 and not visited[ny][nx]:
                dq.append((ny,nx))
                visited[ny][nx] = 1
            elif cheese[ny][nx] ==1 and not visited[ny][nx]:
                cheese[ny][nx] =0
                visited[ny][nx] =1
                Last_piece+=1
    return Last_piece
res=[]
time=0
while True:
    piece = bfs()
    if piece ==0:
        print(time)
        print(res[-1])
        break
    time+=1
    res.append(piece)