[리트코드 994] 썩은 오렌지 — 다중 시작점 너비 우선 탐색

원제: Rotting Oranges

문제 요약

각 분마다 썩은 오렌지와 상하좌우로 맞닿은 신선한 오렌지가 썩는다. 모든 신선한 오렌지가 썩을 때까지 필요한 최소 시간을 반환하고, 끝내 썩지 않는 오렌지가 있으면 -1을 반환한다.

조건과 입출력

grid의 0은 빈 칸, 1은 신선한 오렌지, 2는 썩은 오렌지다. 인접은 상하좌우 네 방향만 의미한다. m == grid.length, n == grid[i].length이며 1 <= m, n <= 10, grid[i][j]는 0, 1, 2 중 하나다. 원문 예제: grid = [[2,1,1],[1,1,0],[0,1,1]]의 출력은 4, grid = [[2,1,1],[0,1,1],[1,0,1]]의 출력은 -1, grid = [[0,2]]의 출력은 0이다.

예제와 문제 자료

예제 1에서는 처음 썩은 오렌지에서 매 분 한 단계씩 퍼져 모든 신선한 오렌지가 4분에 썩는다. 예제 2의 (2,0)은 상하좌우로 썩음이 닿지 않아 -1이다. 예제 3에는 처음부터 신선한 오렌지가 없어 0을 반환한다.

풀이 아이디어

처음부터 썩은 모든 오렌지를 같은 거리 0의 출발점으로 삼고, 큐를 분 단위의 층으로 처리한다. 한 층에서 새로 찾은 신선한 오렌지는 다음 분의 new_queue에 모인다. visited를 큐에 넣는 시점에 표시하므로 같은 칸이 여러 경로에서 중복으로 들어가지 않는다. 썩음은 인접한 신선한 오렌지로만 전파되므로, 탐색이 끝난 뒤에도 방문하지 않은 1이 있다면 그 오렌지는 도달 불가능하다.

코드의 핵심

코드는 n = len(grid)를 행 수, m = len(grid[0])를 열 수로 사용한다. 먼저 모든 2의 좌표를 queue에 넣고 방문 표시한다. 각 반복에서 range(len(queue))만큼 기존 층을 꺼내 네 방향을 확인하며, 범위 안이고 grid[sx][sy] == 1이며 방문하지 않은 경우에만 다음 층에 넣는다.

예제 1의 코드 추적: 초기 층은 (0,0)이다. 새 층이 생길 때마다 answer가 1씩 증가한다.

마지막 새 층까지 처리하면 answer는 4다. new_queue가 비면 더 퍼질 곳이 없으므로 반복을 끝낸다. 이후 전체 격자를 검사해 grid[i][j] == 1 and not visited[i][j]인 칸이 있으면 -1, 없으면 answer를 반환한다.

제출 코드

from collections import deque
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        queue = deque()
        visited = [[False] * m for i in range(n)]
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    visited[i][j] = True
                    queue.append((i,j))
        answer = 0
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        while queue:
            new_queue = deque()
            for i in range(len(queue)):
                x,y = queue.popleft()
                for dx,dy in directions:
                    sx,sy = x+dx,y+dy
                    if 0<=sx<n and 0<=sy<m and grid[sx][sy] == 1 and not visited[sx][sy]:
                        new_queue.append((sx,sy))
                        visited[sx][sy] = True

            if not new_queue:
                break

            answer += 1
            queue = new_queue

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1 and not visited[i][j]:
                    return -1

        return answer

복잡도

행 수를 n, 열 수를 m이라 하면 격자 초기화와 마지막 검사에 O(nm), BFS에도 각 칸을 최대 한 번 방문하므로 전체 시간은 O(nm)이다. visited와 큐의 보조 공간은 각각 최대 O(nm)이다. 별도의 결과 목록은 저장하지 않는다.

복습 포인트

answer는 새 층이 실제로 생길 때만 증가하므로 처음부터 신선한 오렌지가 없거나 퍼질 곳이 없으면 0이다. 방문 여부는 grid 값을 바꾸는 대신 visited로 관리한다. 인접 판정은 대각선을 제외한 네 방향이다.

출처

문제 원문