[백준] 2636 치즈

📖 문제

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

💻 내 코드

import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

cheese=[list(map(int, sys.stdin.readline().split())) for _ in range(H)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]

time=0
cnt=0

def hasC(): # 모든 치즈가 녹았는지 확인
    for i in range(H):
        for j in range(W):
            if cheese[i][j]!=0: # 아직 모두 녹지 않았음
                return True 
    return False

def melt(x, y): # bfs를 이용하여 탐색
    q=deque([])
    q.append((x,y))
    visited[x][y]=True
    while(q):
        x, y=q.pop()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<H and 0<=ny<W and not visited[nx][ny]: 
                visited[nx][ny]=True
                if cheese[nx][ny]==1: # 만약 1이라면 판의 가장자리에서 시작했기 때문에 공기와 접촉한 치즈이므로 
                    cheese[nx][ny]+=1 # 표시

                elif cheese[nx][ny]==0: # 만약 0이라면 아직 치즈를 만나지 못한 것이므로 queue에 append
                    q.append((nx, ny))

def erase(): # 공기와 접촉된 칸은 녹음 
    global cnt
    cnt=0
    for i in range(H):
        for j in range(W):
            if cheese[i][j]>1:
                cnt+=1
                cheese[i][j]=0

while hasC():# 치즈가 모두 녹을때까지 반복
    visited = [[False] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if i==0 or i==H-1 or j==0 or j==W-1:
            # 판의 가장자리에서만 탐색 시작
                melt(i,j)
    time+=1
    erase()


print(time)
print(cnt)

💡 풀이

• 상세 코드 설명은 코드에 적어둠
• 공기와 접촉한 부분을 구하기 위해서는 판의 가장자리에서부터 탐색을 시작해야 한다
• 그래서 판의 가장자리에는 치즈가 없는 것
• bfs를 이용함