[1스4코2파] # 231 LeetCode 994. Rotting Oranges

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (231차)
[4코1파] 2023.01.13~ (223일차)
[1스4코1파] 2023.04.12~ (134일차)
[1스4코2파] 2023.05.03 ~ (112일차)

Today :

2023.08.22 [230일차]
graph
994. Rotting Oranges

LeetCode 994. Rotting Oranges

https://leetcode.com/problems/rotting-oranges/

문제 설명


각 셀이 세 가지 값 중 하나를 가질 수 있는 m x n Grid가 있을 때,
각 세가지 값 중 0은 빈 셀, 1은 신선한 오렌지, 2는 썩은 오렌지(rotten oranges)를 나타냄
1분마다 썩은 오렌지와 4방향으로 인접한 신선한 오렌지는 모두 썩는다고 했을 때,
어떤 셀에도 신선한 오렌지가 없을 때까지 경과해야 하는 최소 시간(분)을 반환하고, 모든 셀을 다 썩게하지 못할 경우 -1를 반환한다.

문제 풀이 방법

이 문제는 bfs 로 풀면서 fresh 한 오렌지와 time을 기록하면서 탐색한다. dfs 니까 queue를 이용해서 풀고, queue나 fresh orange가 None이 될때까지 탐색하면서 time을 증가시킨다.
남은 fresh가 0이면 time을 return 하고 fresh가 0이 아니면 -1 return 하도록 짬
기본적인 bfs 문제임
(근데 이제 나는 답보고 푼 ㅗ)

내 코드

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        q = deque()
        time, fresh = 0,0
        rows, cols = len(grid), len(grid[0])
        directions = [(0,1),(0,-1),(1,0),(-1,0)]

        for r in range(rows):
            for c in range(cols):
                if grid[r][c]==1:
                    fresh +=1
                if grid[r][c]==2:
                    q.append([r,c])

        while q and fresh >0:
            
            for i in range(len(q)):
                r, c = q.popleft()
                for dr, dc in directions:
                    x, y = r+dr, c+dc

                    if (x<0 or x==rows or y<0 or y==cols) or grid[x][y]!=1 :
                        continue
                    grid[x][y] = 2
                    q.append([x,y])
                    fresh -=1

            time +=1

        return time if fresh==0 else -1

        

증빙

여담

dfs는 썩은 오렌지를 표시할 수 없어서 bfs로 풀어야한단다 ㅗ