[Python](BFS) 백준 2636번 : 치즈

---

<접근 방법>

1. 항상 테두리 부분은 공기이므로 항상 (0, 0)을 시작으로 BFS를 돌린다.
2. 시간이 얼마나 걸리는가를 구하기 위해 count라는 변수로 세주고 무한 while문을 돌려준다.
3. BFS를 돌리면서 치즈를 만나면 치즈라는 리스트에 x, y좌표를 넣어주고 q에는 넣어주지 않는다.
   공기를 만나면 q 안에 (x, y)를 넣어줌으로써 계속 q를 돌린다.
4. 이때 cheese에 저장되는 정보가 없으면 무한 반복문을 빠져나가도록 하고 그렇지 않으면 cheese개수 정보를 갱신해주고 가장 테두리 치즈 정보를 담고 있는 치즈 리스트에서 좌표를 꺼내며 공기(arr[x][y]==0)으로 바꿔준다.

from collections import deque

def bfs():
    global answer	# 가장 마지막에 남는 치즈 갱신 위함
    q = deque()
    q.append((0, 0))	# 항상 (0,0) 좌표는 공기이므로 (0,0)에서 시작
    cheese = []
    while q:
        ci, cj = q.popleft()
        for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            ni = ci + di
            nj = cj + dj
            if 0<=ni<N and 0<=nj<M and not visited[ni][nj]:	# 좌표내, 미방문이라면
                if arr[ni][nj] == 0:	# 공기라면
                    q.append((ni, nj))	# 계속해서 q에 넣음
                    visited[ni][nj] = 1
                elif arr[ni][nj] == 1:	# 치즈라면, q에 넣지 않고
                    visited[ni][nj] = 1
                    cheese.append((ni, nj))	# 치즈라는 리스트에 정보 담기
    if not cheese:	# 치즈가 하나도 없다면 --> 이미 다 녹은 상태
        return 1	# 녹은 상태라는 의미로 1을 반환
    answer = len(cheese)	# 치즈가 있다면 최후의 치즈 개수 갱신
    for i, j in cheese:
        arr[i][j] = 0	# 공기에 접촉한 치즈들을 공기로 바꿔줌
    return 0


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
count = 0
answer = 0
while True:
    visited = [[0] * M for _ in range(N)]
    if bfs():
        break
    count += 1
print(count)
print(answer)

이해가 되지 않는 부분이 있으면 질문 주세요. 감사합니다.