Python으로 LeetCode 994. Rotting Oranges (Easy)

LeetCode 994. Rotting Oranges (Easy)

이 문제는 백준 7576. 토마토 문제와 유사하다. 

썩은 오렌지가 신선한 오렌지를 썩게 한다고 하였을 때, 

모든 오렌지가 다 썩으려면 며칠이 걸리는지 그 최소 일수를 구하도록 해야 한다.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

Github에서 코드 보기

문제 조건

주어진 2차원 배열 Grid에는 각각 숫자가 들어 있고, 0은 빈 칸, 1은 신선한 오렌지, 2는 썩은 오렌지를 의미한다.

썩은 오렌지는 상하좌우의 신선한 오렌지를 썩게 만들수 있다.

신선한 오렌지가 모두 사라질 때의 시간을 구해야 하며, 처음부터 신선한 오렌지가 없을 경우에는 0을, 신선한 오렌지는 있으나 썩은 오렌지가 없을 경우에는 -1을 출력해주는 예외처리를 해주어야 한다.

문제 풀이

주어진 grid의 정보를 파악하기 위해 1번 순회하며 신선한 오렌지의 수를 세고, 썩은 오렌지의 경우에는 리스트에 위치 정보를 담아준다.신선한 오렌지가 0일 경우에는 0을 반환하고, 신선한 오렌지는 있으나 썩은 오렌지가 없는 경우는 -1을 반환하여 신선한 오렌지가 썩을 수 있는 경우는 없음을 알려준다.

사전 작업이 끝날 경우, 이제 신선한 오렌지를 썩은 오렌지가 썩게 만들어야 한다. 썩은 오렌지의 위치 정보를 담은 리스트를 pop()  하면서 인접한 상하좌우에 신선한 오렌지가 있는지 확인해보고 썩게 만든다. 신선한 오렌지의 수를 -1 해주고, 만약 신선한 오렌지의 수가 0일 경우에는 현재의 시간을 반환해주면서 함수를 종료한다. 그렇지 않을 경우에는 현재의 시간에 하나의 오렌지라도 썩게 했다는 표시(changed)도 해주어야 하는데, 현재의 time(rotten_orange_position의 모든 인접한 지역에 신선한 오렌지가 있는지 확인했음에도)에 어떤 신선한 오렌지를 발견하지도 못했다면, 시간이 100만번 흘러도 다른 신선한 오렌지를 썩게 못하므로 -1을 출력해주어야 하기 때문이다. 

인전한 오렌지를 썩게하였다면, next_rotten_orange_position에 썩게된 오렌지의 정보를 담아뒀다가, 기존의 rotten_orange_position의 썩은 오렌지의 인접 위치를 다 확인하였을 때에 rotten_oragne_position에 넣어준다. 이 작업을 반복하였을 때, 신선한 오렌지의 수가 0이 되거나(time 반환), 더 이상 신선한 오렌지를 변경시키지 못하는 경우(changed가 False라서 -1 반환) 중에 하나로 결과가 나오게 된다. 

파이썬 코드

 
class Solution:
    def orangesRotting(self, grid) -> int:
        """
        Rumtime : faster than  84% of Python3
        Memory Usage : less tahn 5.12% of Python3
        """
        fresh_orange_count = 0
        rotten_orange_position = []
        next_rotten_orange_position = []
        changed = True
        time = 0
        dr = [-1, 0, 1, 0]
        dc = [0, 1, 0, -1]
 
        # 현재의 상자 정보 확인
        for i in range(len(grid)*len(grid[0])):
            r = i // len(grid[0])
            c = i % len(grid[0])
            v = grid[r][c]
            if v == 1:
                fresh_orange_count += 1
            elif v == 2:
                rotten_orange_position.append((r,c))
 
 
        # 신선한 오렌지가 없는 경우
        if fresh_orange_count == 0:
            return 0
 
        # 신선한 오렌지는 있으나 썩은 오렌지가 없는 경우
        if len(rotten_orange_position) == 0:
            return -1
 
        while changed:
            changed = False
            time += 1
            while rotten_orange_position:
                rotten_orange = rotten_orange_position.pop()
                r, c = rotten_orange
                for i in range(4):
                    temp_r = r + dr[i]
                    temp_c = c + dc[i]
 
                    if 0 <= temp_r < len(grid) and 0 <= temp_c < len(grid[0]):
                        # 신선한 오렌지 썩게 하기
                        if grid[temp_r][temp_c] == 1:
                            grid[temp_r][temp_c] = 2
                            changed = True
                            fresh_orange_count -= 1
 
                            # 모든 오렌지가 다 썩었으면 시간을 반환
                            if fresh_orange_count == 0:
                                return time
                            next_rotten_orange_position.append((temp_r, temp_c))
            rotten_orange_position = next_rotten_orange_position
            next_rotten_orange_position = []
 
        if fresh_orange_count == 0:
            return time
        else:
            return -1
 
 
if __name__ == "__main__":
    s = Solution()
    print(s.orangesRotting([[2,1,1],[1,1,0],[0,1,1]]))
    print(s.orangesRotting([[2,1,1],[0,1,1],[1,0,1]]))
    print(s.orangesRotting([[0,2]]))