[백준/bfs] 2638번: 치즈(다시)

-문제: https://www.acmicpc.net/problem/2638

1. 공기와 접촉하면 천천히 녹는다. 내부에 있는 공간은 접촉하지 않는 것으로 가정한다. 이 의미에 힌트가 있다

2. 내부에 있는 공간은 접촉하지 않으므로 외부에서부터 bfs로 진행해줘서 2번이상 접촉을 하면 다음 반복문에서 제외시켜주면 된다

3. 마지막으로 전체가 0일 때 무한루프를 탈출해준다 

-정답풀이: 

from collections import deque

n,m=map(int,input().split())
cheeze=[list(map(int,input().split())) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
time=0
while True:
    q=deque()
    ch=[[0]*m for _ in range(n)]
    ch[0][0]=1
    q.append([0,0])
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m and not ch[nx][ny]:
                #치즈가 있는 곳
                if cheeze[nx][ny]:
                	#그 치즈와 접하는 공기면 갯수 추가
                    cheeze[nx][ny]+=1 
                #치즈가 없는 곳
                else: #cheeze[nx][ny]==0 
                	#공기가 지나갔다는 표시
                    ch[nx][ny]=1 
                    q.append((nx,ny))
    flag=0
    for i in range(n):
        for j in range(m):
            if cheeze[i][j]>=3:#공기 2면과 닿은 치즈는 없어진다
                cheeze[i][j]=0
            elif 0< cheeze[i][j]:
                flag=1
                cheeze[i][j]=1
    time+=1
    if not flag: #flag가 0일 때 
        print(time)
        break

-풀이 이해:

방문하지 않은 곳을 기준으로 치즈가 있는 영역이면 +1 해준다

 

방문하지 않은 곳인데 치즈가 없다면 방문 표시만 하고, 해당 위치로 이동한다

 

 

elif cheeze 값이 1 또는 2일 경우 공기와 닿는면이 없거나 한변 밖에 없다

 

 

flag가 1이면 아직 사라지지 않은 치즈가 있다는 말이라서 계속 시간을 재면된다 

flag==0이면 치즈가 모두 사라졌다는 의미이므로 time을 출력해준다 

 

 

Q: 그럼 치즈가 없는 곳을 기준으로 이동한다는 말인가?