[BOJ] 2638. 치즈 (🥇, BFS)

🔗

풀이

외부 공기와 2면 이상 맞닿은 치즈들은 사라지게 된다. 모든 치즈가 사라지는데 얼마의 시간이 소요되는지 구하는 문제이다.

최소 시간을 구하며 그래프 탐색이기 때문에 너비 우선 탐색 알고리즘을 사용했다. 이때 외부 공기라는 개념이 뭔지 어떻게 구해야하는지 아이디어를 떠올리는 게 좀 오래걸렸다.

우선 풀이는 다음과 같이 진행했다.

1. 이전에 외부 공기들을 큐에 담고 다음 외부 공기들을 찾는다.
2. 외부 공기들을 큐에 넣고 맞닿은 치즈들을 찾는다. 외부 공기들과 만날 때마다 치즈들의 visited 값을 +1 해준다.
3. 전체 배열을 돌면서 외부 공기들과 만난 값이 2이상인 치즈들을 찾아서 반환한다. 다음 외부 공기가 되는 값들이 된다.

그런데 여기에 내부 공기라는 개념이 들어가면서 좀 꼬였다. 외부 공기가 치즈를 녹이면서 치즈의 내부에 있는 내부 공기들과 만나게 되는데, 내부 공기들은 외부 공기와 만나게 되면 곧바로 맞닿은 치즈들을 사라지게 할 수 있다. 즉, 이미 한 번 치즈들을 사라지게 한 후, 외부 공기와 맞닿아서 사라지게 한 치즈들은 다음 번에 외부 공기가 되는데, 이때의 외부 공기들과 만나게 되는 치즈의 내부에 있는 내부 공기들은 큐에 담겨서 다음 번 연산으로 넘어가는 게 아니라, 이때의 외부 공기들과 합쳐져서 맞닿은 치즈들을 사라지게 해야 한다는 것이다.

앞서 이전에 받았던 외부 공기들에 새롭게 찾은 내부 공기의 위치들을 합쳐서 맞닿은 치즈를 사라지게 하면 된다.

# 치즈

import sys
sys.stdin = open('input.txt')
from collections import deque

def is_valid(x, y):
    return 0 <= x < N and 0 <= y < M

def bfs(queue):
    # 외부 공기 찾기
    next_queue = queue.copy()
    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if not is_valid(nx, ny) or visited[nx][ny] or cheeze[nx][ny]:
                continue
            next_queue.append((nx, ny))
            queue.append((nx, ny))
            visited[nx][ny] = 1

    # 맞닿은 치즈 찾기
    while next_queue:
        x, y = next_queue.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if not is_valid(nx, ny) or not cheeze[nx][ny]:
                continue
            visited[nx][ny] += 1

    cheeze_queue = deque()
    for x in range(N):
        for y in range(M):
            if cheeze[x][y] and visited[x][y] >= 2:
                cheeze_queue.append((x, y))
                cheeze[x][y] = 0
    # for row in cheeze:
    #     print(*row)
    # print(cheeze_queue)
    return cheeze_queue
            
def is_all_find():
    for row in cheeze:
        if sum(row):
            return False
    return True

N, M = map(int, input().split())
cheeze = [list(map(int, input().split())) for _ in range(N)]

queue = deque([(0, 0)])
out_air = deque()
visited = [[0] * M for _ in range(N)]
dx = (0, 1, -1, 0)
dy = (1, 0, 0, -1)


hour = 0
while not is_all_find():
    queue = bfs(queue)
    hour += 1

print(hour)