[Boj | Gold 3 | Python] 치즈

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

문제

치즈가 외부 공기와 두 칸 이상 접촉하면 1시간 뒤 녹는다. 치즈가 다 녹을 때까지 몇 시간 걸리나?

 

풀이과정

치즈 = 1 , 빈 공간 = 0

일단 치즈로 외곽 안에 0인 애들을 조심해야 한다. 무작정 전체 완전탐색으로 BFS 돌렸다가는 안에 0도 같이 카운트에서 녹이면 안 될 것도 녹여버릴 수 있다.

외곽은 -1로 만들어주고, 완전 탐색으로 "외곽"이 두 개 이상 닿는 것을 카운트 해서 -1로 만들어 주면 된다. 그리고 위에 그림3과 같이 치즈 외곽에 막혔다 뚫린 경우를 위해 BFS 탐색을 통해 외곽과 0이 닿으면 0을 -1로 바꿔준다. 

find_melt_cheese의 flag는 1이 없을 때 True를 return 하고 치즈가 남아 있으면 False를 return 한다. 

def find_melt_cheese():
    global n,m
    flag=True
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                flag = False
                air_cnt=0
                for k in range(4):
                    nx=dx[k]+i
                    ny=dy[k]+j
               
                    if 0<=nx<n and 0<=ny<m and graph[nx][ny]==-1:
                        air_cnt+=1

                    if air_cnt>=2:
                        queue.append((i,j))
                        break
    return flag

def aircheck(a,b):
    q.append((a,b))
    graph[a][b]=-1
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=dx[i]+x
            ny=dy[i]+y
            
            if 0<=nx<n and 0<=ny<m and graph[nx][ny]==0:
                graph[nx][ny]=-1
                q.append((nx,ny))

import sys
from collections import deque
input=sys.stdin.readline
n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]

dx=[-1,1,0,0]
dy=[0,0,-1,1]
queue=deque()
q=deque()
answer=0

aircheck(0,0)

while True:
    
    if find_melt_cheese():
        print(answer)
        break
        
    while queue:
        x,y=queue.popleft()
        graph[x][y]=-1
        for k in range(4):
            nx=dx[k]+x
            ny=dy[k]+y
            if 0<=nx<n and 0<=ny<m and graph[nx][ny]==0:
                aircheck(nx,ny)
    answer+=1