Graphs: 994. Rotting Oranges ★★★

994. Rotting Oranges

 

https://youtu.be/y_2x5llfqsE?si=ZrbbbsMQwGQ7Gt-o

 

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        fresh = set()  # 신선한 오렌지 좌표를 저장
        rotten = deque()  # 썩은 오렌지 좌표를 저장
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]  # 4방향 이동

        rows, cols = len(grid), len(grid[0])

        # 1. 초기 상태 설정: 신선한 오렌지와 썩은 오렌지를 구분
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:  # 썩은 오렌지
                    rotten.append((r, c))
                elif grid[r][c] == 1:  # 신선한 오렌지
                    fresh.add((r, c))

        time = 0  # 경과 시간

        # 2. BFS 탐색 시작
        # 이 조건은 썩은 오렌지가 존재하고, 신선한 오렌지가 남아있는 경우에만 루프를 계속 진행함
        # 신선한 오렌지를 모두 썩게 만드는 것이 목표
		# fresh가 비어있으면 모든 신선한 오렌지가 썩었으므로 루프를 종료
		# rotten이 비어있으면 썩은 오렌지가 더 이상 확산될 수 없으므로 루프를 종료합니다.
        while rotten and fresh:
            for _ in range(len(rotten)):
                r, c = rotten.popleft()  # 썩은 오렌지의 위치를 큐에서 꺼냄
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    # 신선한 오렌지가 썩게 되는 조건
                    if (nr, nc) in fresh:
                        fresh.remove((nr, nc))  # 신선한 오렌지를 제거
                        rotten.append((nr, nc))  # 썩은 오렌지로 추가
            time += 1  # 1분 경과

        # 3. 결과 반환
        return time if not fresh else -1

 

while fresh and rotten:

둘다 있으면 while 문 돌고,

fresh 또는 rotten 중 하나가 다 없어지면 멈춤

 

 

조금 다른..스타일.. BFS

 

from collections import deque
from typing import List

class Solution:
    def printOrange(self, grid):
        # 현재 grid 상태를 출력
        # Print the current state of the grid
        for r in range(len(grid)):
            print(grid[r])

    def orangesRotting(self, grid: List[List[int]]) -> int:
        # 0: 빈 셀 (Empty cell)
        # 1: 신선한 오렌지 (Fresh orange)
        # 2: 썩은 오렌지 (Rotten orange)
        # 썩은 오렌지가 시간이 지남에 따라 4방향으로 퍼집니다.
        # Rotten oranges spread in 4 directions over time.
        # 모든 오렌지가 썩는 데 걸리는 시간을 계산합니다.
        # Calculate the time it takes for all oranges to rot.
        # 불가능하면 -1을 반환합니다. Return -1 if not all oranges can rot.

        M, N = len(grid), len(grid[0])  # 행과 열의 크기 저장 (Grid dimensions)

        def bfs(grid):
            fresh = set()  # 신선한 오렌지의 위치를 저장 (Stores positions of fresh oranges)
            rotten = deque()  # 썩은 오렌지의 위치를 저장 (Stores positions of rotten oranges)
            elapse_time = 0  # 경과 시간 초기화 (Initialize elapsed time)

            # 초기 상태에서 신선한 오렌지와 썩은 오렌지의 위치를 분류합니다.
            # Categorize the positions of fresh and rotten oranges initially.
            for r in range(M):
                for c in range(N):
                    if grid[r][c] == 1:  # 신선한 오렌지
                        fresh.add((r, c))
                    elif grid[r][c] == 2:  # 썩은 오렌지
                        rotten.append((r, c))

            # 신선한 오렌지가 없으면 바로 0 반환
            # If there are no fresh oranges, return 0 immediately.
            if not fresh:
                return 0

            # BFS로 썩은 오렌지 확산
            # Use BFS to spread the rotten oranges.
            while rotten:
                for _ in range(len(rotten)):  # 현재 레벨의 모든 썩은 오렌지를 처리 (Process all rotten oranges in the current level)
                    r, c = rotten.popleft()

                    # 4방향으로 퍼뜨리기 (Spread in 4 directions)
                    for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        R, C = r + dr, c + dc
                        # 유효한 범위 내에서 신선한 오렌지를 썩게 만듦
                        # Rot fresh oranges within valid boundaries.
                        if R in range(M) and C in range(N) and grid[R][C] == 1:
                            fresh.remove((R, C))  # 신선한 오렌지 집합에서 제거
                            rotten.append((R, C))  # 새로 썩은 오렌지를 큐에 추가
                            grid[R][C] = 2  # 오렌지를 썩게 표시

                # 한 레벨이 끝나면 시간을 증가시킴
                # Increment time after processing one level.
                elapse_time += 1

                # 남은 신선한 오렌지가 없으면 경과 시간 반환
                # If there are no fresh oranges left, return the elapsed time.
                if not fresh:
                    return elapse_time

            # 썩지 않은 신선한 오렌지가 남아있다면 -1 반환
            # Return -1 if there are fresh oranges that cannot rot.
            return -1

        return bfs(grid)

 

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        fresh = set()
        rotten = deque()

        ROWS, COLS = len(grid), len(grid[0])

        # 4방향
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    fresh.add((r, c))
                if grid[r][c] == 2:
                    rotten.append((r, c))
        minutes = 0

        # 둘다 있으면 while 문 돌고, fresh 또는 rotten 중 하나가 다 없어지면 멈춤
        while fresh and rotten: 
            for _ in range(len(rotten)):
                r, c = rotten.popleft() # rotten을 하나씩 꺼내면서, 확장
                for dr, dc in directions:
                    R, C = r+dr, c+dc

                    if R in range(ROWS) and C in range(COLS) and (R, C) in fresh:
                        fresh.remove((R, C))
                        rotten.append((R, C))
            minutes +=1

        print(fresh)
        return minutes if not fresh else -1

 

최종 코드

좋아요! 이 문제도 전형적인 BFS 시뮬레이션 문제예요.
한 번에 여러 곳에서 동시에 썩기 시작하기 때문에,
멀티 소스 BFS (여러 시작점으로 동시에 퍼짐) 방식으로 풀어야 합니다.

---

✅ 풀이 핵심 아이디어:

• 2인 썩은 오렌지들을 모두 BFS의 시작점으로 넣음
• 매 1분마다, 썩은 오렌지로 인해 인접한 1이 썩음 → 1 → 2 로 바뀜
• BFS 단계가 한 번 끝날 때마다 minutes += 1
• 모든 1이 2가 되면 끝,
  만약 끝나도 1이 남아 있으면 → -1 리턴

✅ BFS + visit set  사용 코드

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        queue = deque()
        visit = set()
        fresh = 0  # 신선한 오렌지 개수

        # 초기 상태: 썩은 오렌지는 큐에 넣고, fresh는 세기
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 2: # 섞은 오렌지: 큐에 넣고
                    queue.append((r, c, 0))  # (행, 열, 시간)
                    visit.add((r, c))        # 섞은 것은 방문처리 해줌
                elif grid[r][c] == 1: # 신선한 오렌지: counting
                    fresh += 1

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        time = 0

        while queue:
            r, c, t = queue.popleft()
            time = max(time, t)  # 현재까지 걸린 시간 기록

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
				# 유효한 행렬 범위에 있고, 신선하며, 방문처리 안됬으면
                if (
                    0 <= nr < ROWS and 0 <= nc < COLS and
                    grid[nr][nc] == 1 and
                    (nr, nc) not in visit
                ):
                    visit.add((nr, nc)) # 방문 처리 하고
                    fresh -= 1 # 신선한것 개수 감소
                    
                    # 섞은 것으로 추가, 
                    # 시간 추가시, 이전 load 된 신선한것 시간 +1
                    queue.append((nr, nc, t + 1)) 

        # 큐가 나왔다는 것은, 섞은 것..으로 확장 처리 모두 끝났다는 의미
        # 신선한것이 없으면(0) 누적된 time 리턴, 
        # 확장 처리 끝났는데, 신선한것이 남았으면, -1 리턴
        return time if fresh == 0 else -1

 

💡 포인트 요약:

• grid 자체는 수정 안 함 (따라서 값은 여전히 1, 2 그대로 유지)
• visit으로 이미 썩은 오렌지 or 전염된 오렌지 관리
• 신선한 오렌지 수를 줄여서 전부 썩었는지 판단