백준 2638 치즈 Python (BFS 풀이)

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

2638번: 치즈

오 어제 풀었던 백준 5547 일루미네이션 문제와 상당히 유사한 접근법으로 풀이하면 되는 BFS/DFS문제였다. 

[ 문제 풀이 아이디어 ]
i) 0과 인접한 1 찾기 
공기 칸(값이 0인 칸)을 중심으로 bfs 탐색을 하고, 공기 칸이 치즈 칸 (값이 1 인 칸)을 만나게 되면 치즈칸에 += 1을 해준다. 

탐색이 종료되었을 때 array[i][j] 의 값이 3이상이면 맞닿는 공기 칸이 2개 이상이라는 의미이므로, 치즈가 사라진다. 
이때의 array[i][j] 를 0으로 바꿔준다. 

ii) bfs 실행횟수 구하기 

while True:
    # bfs 실행할 떄마다 visited 함수 초기화하기
    visited = [[False] * m for _ in range(n)]
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = True

    flag = False  # cheese 남아있는지 여부

bfs문으로 2차원 array를 탐색한다. 
문제에서는 모든 치즈가 사라질때까지의 bfs 실행 횟수를 구해주어야 하므로, while문 안에서 bfs를 실행시키고, 
cheese가 여전히 있으면 flag = True 로 표시하여 치즈가 아직 남아있다는 여부를 표시한다. 
또한 bfs가 실행될때마다 visited 함수를 새롭게 초기화해주어야 한다. 

flag 가 False값이면 while문을 종료한다. 

iii) 치즈가 남아있는지 여부 확인하기 

for i in range(n):
    for j in range(m):
        if array[i][j] >= 3: # 자기자신 1 + 공기 2 이상인 경우 이므로 3이상
            array[i][j] = 0 # vanish cheese
        elif array[i][j] > 0: # 맞닿은 벽이 2개 미만인 치즈는 다시 1로 바꿔준다.
            array[i][j] = 1
            # 아직 cheese가 남아 있음
            flag = True

bfs를 한번 실행한 이후 2차원 배열인 array에 남아있는 값을 확인한다. 
array[i][j] 값이 3이상인 경우, 자기자신 1 포함 + 2개 공기 칸이 이상맞닿았다는 의미이므로 치즈가 녹는다. 
array[i][j] 값이 1 또는 2 인경우 인접한 공기의 칸이 2개 미만이므로, 아직 치즈가 남아있다. 
따라서 flag 를 True로 바꾸어 준다. 

# 2638 치즈
from collections import deque
import sys

# 입력
n, m = map(int, input().split())
array = []
for _ in range(n):
    array.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0 # bfs 실행 횟수 세기

while True:
    # bfs 실행할 떄마다 visited 함수 초기화하기
    visited = [[False] * m for _ in range(n)]
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = True

    flag = False  # cheese 남아있는지 여부

    while queue: # cheese가 모두 없어질 때가지 bfs를 실행한다.
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                if array[nx][ny]: # air칸이 발견한 cheese칸 1 이상의 값이 들어감
                    array[nx][ny] += 1
                else: # air 칸은 계속 탐색하기 위해서 queue에 넣기
                    visited[nx][ny] = True
                    queue.append((nx, ny))

    for i in range(n):
        for j in range(m):
            if array[i][j] >= 3: # 자기자신 1 + 공기 2 이상인 경우 이므로 3이상
                array[i][j] = 0 # vanish cheese
            elif array[i][j] > 0: # 맞닿은 벽이 2개 미만인 치즈는 다시 1로 바꿔준다.
                array[i][j] = 1
                # 아직 cheese가 남아 있음
                flag = True
    answer += 1

    if not flag:
        print(answer)
        break