[Python] 백준 2636 치즈 (BFS)

📌 문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

예제 입력 1

13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

예제 출력 1

3
5

📌 풀이

💬 Code

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

def bfs():
    q = deque([(0, 0)])
    melt = deque([])
    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 and not visited[nx][ny]:
                visited[nx][ny] = 1
                if cheeze[nx][ny] == 0:  # 공기면 계속 탐색하기 위해 큐에 넣음
                    q.append((nx, ny))
                elif cheeze[nx][ny] == 1:  # 치즈면 한 번에 녹이기 위해 melt에 넣음
                    melt.append((nx, ny))
                    
    for x, y in melt:
        cheeze[x][y] = 0  # 공기와 닿은 치즈를 한 번에 녹임
    return len(melt)  # 녹인 치즈 갯수 리턴

n, m = map(int, input().split())
cheeze = []
cnt = 0
for i in range(n):
    cheeze.append(list(map(int, input().split())))
    cnt += sum(cheeze[i])  # 전체 치즈 갯수 카운트
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

time = 1
while True:
    visited = [[0] * m for _ in range(n)]
    meltCnt = bfs()
    cnt -= meltCnt
    if cnt == 0:  # 치즈를 다 녹였으면
        print(time, meltCnt, sep='\n')  # 시간과 직전에 녹인 치즈 갯수를 출력
        break
    time += 1

💡 Solution

외부 공기와 접촉한 치즈만을 녹이려면, 값이 0인 부분에 대해서만 BFS를 진행하면 된다.

👉 BFS

BFS 시작 지점은 어디로 해야 할까? 판의 가장자리에는 치즈가 놓여 있지 않다는 조건이 주어졌으므로 가장자리의 어느 한 지점에서부터 탐색을 진행하면 된다. 본 코드에서는 (0, 0)에서부터 진행한다.

(0, 0)에서 시작해 상하좌우의 좌표 (nx, ny)를 각각 살피고, (nx, ny)에 놓인 값이 0이라면 공기라는 것이므로 계속 탐색하기 위해 q에 넣는다.

(nx, ny)에 놓인 값이 1이라면 공기와 맞닿은 치즈라는 것이므로 녹이기 위해 melt에 넣는다. 바로 녹이지 않는 이유는, 이 상황에서 바로 녹여버리면 (nx, ny) 주변의 치즈가 (nx, ny)를 공기로 인식해버리기 때문이다. 한 타임에 한 번, 공기와 맞닿은 치즈를 한꺼번에 녹여야 한다.

q가 비면 모든 공기를 탐색했다는 것이므로 이제 melt에서 좌표를 꺼내 공기와 맞닿은 치즈를 모두 녹여준다. 그리고 녹인 치즈의 갯수를 리턴한다.

👉 Main

치즈가 다 녹았을 때 걸린 시간과 다 녹기 직전에 놓여있던 치즈 갯수를 출력해야 한다.

치즈가 다 녹았는지는 어떻게 캐치할 수 있을까? 판의 초기 상태에서 치즈의 갯수를 먼저 카운트해 cnt 변수에 저장해둔다. 그리고 BFS 함수로부터 녹인 치즈의 갯수를 리턴받으므로 그것을 meltCnt 변수에 저장한다. cnt에서 meltCnt를 빼면 현재 남아있는 치즈 갯수가 되므로 이 값이 0이면 탐색을 멈추고 시간과 meltCnt를 출력한다.