백준 2636번 : 치즈 in Python

2636번: 치즈

 

www.acmicpc.net

이 문제는 공기에 닿으면 녹는 치즈가 직사각형 모양의 판에 있을 때 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여 있는 칸의 개수를 구하는 문제이다. 단, 치즈 조각은 정사각형 모양의 칸 안에 들어있고 공기에 닿는 면이 하나라도 있으면 한 시간 후에 녹는다. 그리고 치즈로 둘러싸인 빈 공간은 공기가 없다고 가정한다.

이는 BFS 탐색을 이용해 쉽게 해결할 수 있다. 우선 판의 둘레 부분은 항상 공기로 이루어져 있으므로 판의 둘레 부분 중 아무데서나 BFS를 시작해 모든 공기층을 탐색한다. 그리고 치즈 조각 중 이 공기층과 맞닿아 있는 조각들을 없앤다. 이 과정을 모든 치즈가 사라질 때까지 반복하면 된다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 판 내에서 공기층을 찾는 함수로 BFS 탐색을 이용한다.
def find_air():
    # 각 정사각형 칸이 공기가 있는지를 나타내는 행렬
    air_check = [[False]*M for _ in range(N)]
    queue = deque()
    queue.append([0, 0])
    air_check[0][0] = True
    # BFS 탐색 수행
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if 0<=next_x<N and 0<=next_y<M and not visited[next_x][next_y] and board[next_x][next_y] == 0:
                queue.append([next_x, next_y])
                visited[next_x][next_y] = True
                air_check[next_x][next_y] = True
    return air_check
# 치즈 조각 주변에 공기가 있는지를 조사하고 조각을 없앨지 판단하는 함수
def remove_cheeze(x, y):
    global board
    air_around = False
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if 0<=next_x<N and 0<=next_y<M and air[next_x][next_y]:
            air_around = True
    if air_around:
        board[x][y] = 0
    return air_around
# 치즈가 모두 사라질 때까지 걸리는 시간을 저장하는 변수
time = 0
# 한 시간마다 치즈가 녹는 과정을 치즈가 모두 녹을 때까지 계속 반복한다.
while True:
    # BFS 탐색을 보조하는 행렬
    visited = [[False]*M for _ in range(N)]
    # 치즈 조각이 있는 정사각형 칸의 개수를 나타내는 변수
    cnt = 0
    air = find_air()
    # 녹은 치즈가 있는지를 검사한다.
    cheeze_removed = False
    for i in range(N):
        for j in range(M):
            if board[i][j] == 1:
                cnt += 1
                if remove_cheeze(i, j):
                    cheeze_removed = True
    # 녹은 치즈가 없으면 while loop을 빠져나온다.
    if not cheeze_removed:
        break
    time += 1
    # 치즈가 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여 있는 칸의 개수를 세기 위해 따로 저장해 둔다.
    prev_cnt = cnt
print(time)
print(prev_cnt)