[백준] 2638번(파이썬) 치즈

2638번 문제
BFS탐색 문제이다.

문제를 간략히 정리해보면,
1. 치즈의 4변중 2변이상이 공기와 접촉하면, 한 시간만에 녹는다.
2. 치즈 내부 공간은 외부 공기와 접촉하지 않는 것으로 가정한다.
3. 가장자리는 치즈가 놓이지 않는것으로 가정한다.

내가 처음 문제를 접했을 때는 치즈의 시작점을 찾고, 치즈 내에서 BFS 탐색을 진행하는 방식으로 접근했다.
하지만, 그렇게 접근했을 때 치즈 내부공간의 탐색에 어려움을 느꼈다.
그래서 다른 방식의 접근이 필요하다고 느꼈다.
아마 처음에 문제를 접하면 나와 비슷한 방식으로 접근해보지 않을까 조심스럽게 생각해본다..

문제 핵심

이번 문제의 핵심은 치즈를 탐색하는것이 아닌, 공기를 탐색하는 것이다.

공기->공기로 탐색하다가, 치즈면을 만나면 그 치즈면을 몇번 방문했는지 방문정보를 업데이트 시켜주는 것이다.
그렇게 한다면, 치즈 내부공간은 녹을 걱정을 하지 않아도 된다.(외부 치즈에서 큐정보를 업데이트 하지 않기 때문)

그럼 코드로 한번 이해해보자.

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

#공기 탐색
def air_bfs(i,j):
    q=deque()
    q.append([i,j])
    visited[i][j]=1

    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m:
            	#다음 진행이 공기면(큐 추가, 방문처리)
                if visited[nx][ny]==0 and real_graph[nx][ny]==0:
                    q.append([nx,ny])
                    visited[nx][ny]=1
                #다음 진행이 치즈면(방문정보 업데이트)
                elif real_graph[nx][ny]==1:
                    visited[nx][ny]=visited[nx][ny]+1

n, m=map(int, input().split())
real_graph=[]
for i in range(n):
    real_graph.append(list(map(int, input().split())))

dx=[-1,1,0,0]
dy=[0,0,-1,1]
time=0

while 1:
    visited=[[0 for _ in range(m)] for _ in range(n)]

    air_bfs(0,0)
    #탐색 한바퀴 끝나면 시간+1
    time+=1
	
    #두면이상 공기랑 닿으면, 빈칸 처리
    for i in range(n):
        for j in range(m):
            if visited[i][j]>=2:
                real_graph[i][j]=0

    # 공기 카운트
    block_cnt=0
    for i in range(n):
        for j in range(m):
            if real_graph[i][j]==0:
                block_cnt+=1
    #탐색 한번 하고 난 그래프의 공기수가 배열의 크기랑 같으면 break
    if block_cnt==(n*m):
        break
    

print(time)

이번 문제의 심화버전(?)으로 2636 치즈 문제도 풀어보면 좋을 것 같다.