Rotting Oranges

+10

같은 길이의 행 목록으로 격자가 주어집니다. 각 셀은 0(빈칸), 1(신선한 오렌지) 또는 2(썩은 오렌지)입니다. 매분, 위, 아래, 왼쪽 또는 오른쪽으로 썩은 오렌지와 변을 맞대고 있는 신선한 오렌지는 모두 썩습니다. 신선한 오렌지가 하나도 남지 않을 때까지 걸리는 분 수를 반환하거나, 썩지 않는 신선한 오렌지가 있다면 -1을 반환하세요. 처음부터 신선한 오렌지가 없는 격자에는 0분이 필요합니다.

함수

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: 격자, 각 행마다 0, 1, 2로 이루어진 목록 하나
반환값integer: 오렌지가 하나도 신선하지 않을 때까지의 시간(분), 그런 일이 절대 일어나지 않으면 -1

제약 조건

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
모든 행의 길이는 같습니다.
각 grid[i][j]는 0, 1 또는 2입니다.

예제

입력: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
출력: 6
설명: 셀을 (행, 열)로 표기하면, 부패는 (0,0)에서 시작해 유일한 경로를 따라갑니다. 1분에는 (0,1), 2분에는 (0,2)와 (1,1), 3분에는 (2,1), 4분에는 (2,0)과 (2,2), 5분에는 (2,3)에 도달합니다. (1,3)에 있는 오렌지는 (2,3)에만 닿으므로, 6분에 마지막으로 부패합니다.

제출 시 숨은 테스트 +21개

후속 질문

신선한 오렌지마다 이웃한 오렌지가 썩은 후 썩는 데 걸리는 시간이 다르다고 가정해 보세요. 그렇다면 완료 시간을 어떻게 구할 수 있을까요?

풀이

썩음은 모든 썩은 오렌지에서 동시에 시작해 1분에 한 칸씩 퍼지므로, 답은 거리입니다. 가장 먼 신선한 오렌지가 가장 가까운 썩은 오렌지에서 몇 단계 떨어져 있는지를 구하면 됩니다. 시작하기 전에 모든 썩은 오렌지를 큐에 넣고, 한 번에 한 레벨씩, 1분씩 큐를 처리하면 너비 우선 탐색으로 정확히 이 거리를 측정할 수 있습니다.

분 단위로 시뮬레이션하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

설명에 나온 대로 하세요. 매분 전체 격자를 훑어 썩은 오렌지와 맞닿아 있는 모든 신선한 오렌지를 목록으로 만드세요. 그런 다음 목록에 있는 오렌지를 모두 썩게 하고, 시계에 1을 더한 뒤 다시 훑으세요. 썩게 할 오렌지가 더 이상 발견되지 않을 때까지 반복하세요. 그 시점에도 격자에 신선한 오렌지가 남아 있다면 썩음이 그 오렌지에 절대 도달할 수 없으므로 -1을 반환하세요.

먼저 목록을 만든 다음 썩게 하세요. 훑는 도중에 오렌지를 썩게 하면, 같은 훑기에서 나중에 확인하는 칸이 그 오렌지를 썩은 상태로 보고 자신도 썩게 됩니다. 그러면 썩음이 1분 만에 여러 칸을 빠르게 지나가 시계 값이 너무 작아집니다.

이 방법은 올바르지만, 매분 행 × 열 개의 칸을 전부 훑어야 하며, 걸리는 시간은 칸의 개수에 가까워질 수 있습니다. 신선한 오렌지가 하나의 구불구불한 경로를 이루고 그 시작점에 썩은 오렌지가 있는 150 × 150 격자에서는 썩음이 진행되는 데 11,324분이 걸립니다. 즉, 22,500개의 칸을 11,324번 훑어야 하므로 약 2.5 × 10^8번 칸을 확인해야 하며, 그중 거의 대부분은 상태가 바뀔 수 없는 칸입니다.

알고리즘

분을 0으로 설정합니다.
격자를 살펴보고 썩은 이웃이 있는 모든 신선한 오렌지를 목록에 추가합니다.
목록이 비어 있으면 중단합니다. 그렇지 않으면 목록에 있는 모든 오렌지를 썩게 만들고 분에 1을 더한 다음 다시 살펴봅니다.
신선한 오렌지가 남아 있으면 -1을 반환하고, 그렇지 않으면 분을 반환합니다.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

레벨별 다중 소스 BFS

핵심 아이디어

스캔은 작업이 일어나는 곳에서 멀리 떨어진 셀에 시간을 낭비합니다. t+1분에 썩을 수 있는 오렌지는 t분에 썩은 오렌지의 신선한 이웃뿐입니다. 그러니 썩음의 경계인 이 오렌지들만 큐에 담아두세요.

0분에 이미 썩어 있는 오렌지를 모두 큐에 넣고 시작합니다. 이것이 다중 시작점 부분입니다. 신선한 오렌지는 가장 가까운 썩은 오렌지까지의 거리에 해당하는 분에 썩으며, 모든 시작점을 넣고 시작한 너비 우선 탐색은 각 셀에 가장 가까운 시작점에서 먼저 도달합니다. 시작점마다 탐색한 뒤 최솟값을 구하는 대신, 한 번의 탐색으로 같은 작업을 할 수 있습니다.

그런 다음 레벨 단위로 처리합니다. 1분이 시작될 때 큐에는 k개의 오렌지가 들어 있는데, 이들은 지난 분에 썩은 오렌지입니다. 앞에서 정확히 k개를 꺼내고, 각 오렌지에 대해 신선한 이웃을 썩게 한 다음 큐의 뒤에 추가합니다. k개를 모두 처리하면 1분이 지난 것이고, 큐에는 다음 경계가 들어 있습니다. 첫 번째 예제의 레벨은 {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}입니다. 시작 후 여섯 단계이므로 6분이 걸립니다.

처음에 신선한 오렌지의 수를 세고, 오렌지가 썩을 때마다 그 수를 줄이세요. 수가 0이 되는 즉시 멈추세요. 그렇지 않으면 아무것도 썩지 않는 시간까지 1분으로 세게 됩니다. 신선한 오렌지 수가 0보다 큰 상태에서 큐가 비면 -1을 반환하세요. 각 셀은 큐에 최대 한 번 들어가고 이웃 네 곳을 확인하므로, 작업량은 O(rows × cols)입니다.

알고리즘

썩은 오렌지를 모두 큐에 넣고 신선한 오렌지의 개수를 센다.
분을 0으로 설정한다. 큐가 비어 있지 않고 신선한 오렌지가 남아 있는 동안 분을 1 늘리고 큐의 크기 k를 기록한다.
앞에서 오렌지 k개를 꺼낸다. 그리드 안에서 이웃한 신선한 오렌지마다 썩은 상태로 표시하고, 신선한 오렌지 개수를 줄인 다음 큐의 뒤에 추가한다.
루프가 끝나면 신선한 오렌지의 개수가 0이면 분을 반환하고, 그렇지 않으면 -1을 반환한다.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

함정과 경계 사례

여기서 오답이 나오는 대부분의 경우는 시간이 1분 차이 나거나, 탐색을 잘못된 위치에서 시작했기 때문입니다.

마지막 단계에 1분을 더하는 경우. 큐가 빌 때까지 반복문이 실행되면 마지막 반복에서는 아무것도 썩지 않는데도 1분이 더해집니다. 썩지 않은 신선한 오렌지가 더 이상 없으면 즉시 멈추세요.
썩은 오렌지마다 차례로 탐색하는 경우. 첫 번째 탐색은 도달하는 모든 오렌지를 자체 시간으로 처리하므로, 중간에서 만나야 하는 두 시작점이 있으면 시간이 너무 크게 나옵니다. [[2, 1, 1, 1, 1, 1, 1, 2]]는 6분이 아니라 3분이 걸립니다.
분 단위 버전에서 스캔하는 동안 오렌지를 썩게 만드는 경우. 그러면 같은 스캔에서 나중에 처리되는 칸이 해당 오렌지를 이미 썩은 것으로 보고, 1분 만에 여러 칸을 거쳐 썩음이 퍼집니다.
썩은 오렌지가 없다는 이유로 -1을 반환하는 경우. 신선한 오렌지도 없다면 아무 일도 일어날 필요가 없습니다. [[0]]은 0을 반환합니다. 썩지 않고 남은 신선한 오렌지가 있을 때만 답은 -1입니다.
오렌지를 큐에 넣을 때가 아니라 꺼낼 때 썩은 것으로 표시하는 경우. 그러면 썩은 오렌지 두 개와 인접한 오렌지가 큐에 두 번 들어가고 신선한 오렌지의 수가 0보다 작아집니다.
깊이 우선 탐색. 가능한 한 깊게 한 경로를 따라가므로, 오렌지에 처음 도달한 시점으로는 그 오렌지가 몇 분 만에 썩는지 알 수 없습니다.

자주 묻는 질문4

썩어 가는 오렌지의 시간 복잡도는 무엇인가요?

너비 우선 탐색을 사용하면 O(rows × cols)입니다. 첫 번째 순회에서 모든 셀을 한 번씩 살펴보고, 각 오렌지는 큐에 최대 한 번 들어가며 네 개의 이웃을 확인합니다. 최악의 경우, 즉 격자가 썩은 오렌지로 가득 찬 경우 큐는 O(rows × cols)의 공간을 차지합니다.

Rotting Oranges에서는 왜 DFS가 아니라 BFS를 사용할까요?

너비 우선 탐색은 시작점으로부터의 거리에 따라 셀을 방문하며, 여기서 거리는 시간입니다. 탐색의 k 레벨은 정확히 k분에 썩는 오렌지들의 집합입니다. 깊이 우선 탐색은 짧은 경로를 찾기 전에 긴 우회 경로를 따라 셀에 도달할 수 있으므로, 더 짧은 경로를 찾을 때마다 셀을 다시 방문해야 합니다.

다중 소스 BFS란 무엇인가요?

큐에 하나가 아닌 여러 셀을 거리 0으로 넣고 시작하는 너비 우선 탐색입니다. 한 번의 탐색으로 모든 셀에서 가장 가까운 출발점까지의 거리를 구합니다. 이는 출발점마다 탐색한 뒤 최솟값을 취한 결과와 같지만, 탐색은 한 번만 수행합니다. 격자에서 "가장 가까운 X까지의 거리"를 묻는 문제라면 모두 이 방법을 사용합니다.

격자를 변경하지 않고 썩은 오렌지 문제를 풀 수 있나요?

네. 별도의 방문 배열을 두고 격자에 2를 쓰는 대신 그 배열을 확인하세요. 이렇게 하면 O(rows × cols)의 추가 메모리가 필요하며, 큐에도 어차피 이만큼의 메모리가 필요할 수 있습니다. 격자를 참조로 전달하는 언어에서는 격자에 값을 쓰면 호출한 쪽의 격자도 변경되므로, 면접관이 이에 관해 질문할 수 있습니다.

Python

def orangesRotting(grid):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]

기대값