a-085-rotting-oranges2026-08-12mediumleetcode #994neetcode150

썩은 오렌지

#array#breadth-first-search#matrix

문제

· problem

P.a-085-rotting-oranges

썩은 오렌지

m × n 격자가 주어집니다. 각 셀은 다음 세 가지 값 중 하나를 가질 수 있습니다: - 0: 빈 셀 - 1: 신선한 오렌지 - 2: 썩은 오렌지 매 분마다, 상하좌우로 인접한(4방향) 썩은 오렌지와 접한 신선한 오렌지는 썩게 됩니다. 신선한 오렌지가 남아있지 않을 때까지 경과해야 하는 최소 분 수를 반환하세요. 만약 신선한 오렌지를 모두 썩게 할 수 없다면 -1을 반환하세요.

제약

· 1 ≤ m, n ≤ 10
· grid[i][j] is 0, 1, or 2
· m == grid.length
· n == grid[i].length

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[[2,1,1],[1,1,0],[0,1,1]]

example 2input → output

[[2,1,1],[0,1,1],[1,0,1]]

-1

example 3input → output

[[0,2]]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
4방향 인접이란 정확히 무엇을 의미하나요?
☐
입력 격자를 수정할 수 있나요?
☐
처음부터 신선한 오렌지가 없다면 답은 무엇인가요?
☐
일부 신선한 오렌지에 도달할 수 없다면?
☐
오렌지는 대각선 방향으로도 썩나요?
☐
썩는 순서가 결과에 영향을 미치나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 큐 초기화

○

q = collections.deque()

○

q = []

○

q = set()

step 2· 초기 썩은 오렌지 큐에 추가│ 중첩

○

q.append((r, c))

○

q.append([r, c])

○

# 큐에 추가하지 않음

step 3· BFS 루프 조건

○

while fresh > 0 and q:

○

while q:

○

while fresh > 0:

step 4· 현재 레벨 크기 스냅샷│ 중첩

○

length = len(q)

○

for i in range(len(q)): # 루프 중 길이 변경

○

length = len(q) - 1

step 5· 4방향 확인│ │ 중첩

○

for dr, dc in directions:

○

# (r-1,c), (r+1,c), (r,c-1), (r,c+1)을 각각 4개 if문으로 확인

○

for dr, dc in [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]]:

step 6· 신선한 오렌지 검증 및 표시│ │ │ 중첩

○

and grid[row][col] == 1

○

and grid[row][col] != 0:

○

and grid[row][col] > 0:

step 7· 시간 증가│ 중첩

○

time += 1

○

time += 1  # 내부 for 루프 (i in range(length)) 안에서

○

# time 증가 없음

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def orangesRotting(self, grid: List[List[int]]) -> int:

        q = collections.deque()

        fresh = 0

        time = 0

        for r in range(len(grid)):

            for c in range(len(grid[0])):

                if grid[r][c] == 1:

                    fresh += 1

                if grid[r][c] == 2:

                    q.append((r, c))

        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        while fresh > 0 and q:

            length = len(q)

            for i in range(length):

                r, c = q.popleft()

                for dr, dc in directions:

                    row, col = r + dr, c + dc

                    # if in bounds and nonrotten, make rotten

                    # and add to q

                    if (

                        row in range(len(grid))

                        and col in range(len(grid[0]))

                        and grid[row][col] == 1

):

                        grid[row][col] = 2

                        q.append((row, col))

                        fresh -= 1

            time += 1

        return time if fresh == 0 else -1

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[[2,1,1],[1,1,0],[0,1,1]]

→

case 2

[[2,1,1],[0,1,1],[1,0,1]]

→

-1

case 3

[[0,2]]

→

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.