Leetcode 994. Rotting Oranges with Python

문제

You are given an m x n grid where each cell can have one of three values:

0. representing an empty cell,
1. representing a fresh orange, or
2. representing a rotten orange.
3. Every minute, any fresh orange
   that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. 
If this is impossible, return -1.

m * n 2차원 배열에 세가지 종류의 값이 있다.

0. 비어있는 셀을 의미한다.
1. 신선한 오렌지를 의미한다.
2. 상한 오렌지를 의미한다.

매 분마다 상한 오렌지의 상하좌우에 4방향에 위치한 오렌지가 썩는다.

모든 오렌지가 썩는데 걸리는 분을 리턴하시오, 만약 오렌지가 전부 썩을수 없다면 -1을 리턴하시오.

예시

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

제한

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

풀이법

1. 판을 하나 더 만들기

우리에게는 오렌지가 잔뜩 자라는 2D 배열이 존재하는데

이 배열을 그대로 복사하여 임시 배열을 하나 더 두는것이다.

원래 배열을 전부 순회하면서 상한 오렌지가 있을 경우 원본 배열은 가만히 두고 새로운 배열의 상해야 할 오렌지만
상하게 한다. 1분 내에 상한 오렌지의 갯수를 저장해 놓는다.

이걸 원본의 전체 오렌지에 반복할시 임시 배열은 원본 배열의 1분 후 모습이 될 것이다.

이때 1분 내 상한 오렌지가 존재하지 않는다면 더이상 상할수가 없다는 뜻이 되는데

상한 오렌지가 없으면서 신선한 오렌지가 안에 있으면 전부 상하게 하지 못한다는 것으로 -1 리턴

상한 오렌지가 없으면서 신선한 오렌지도 없으면 전부 상한것으로 지금까지 반복한 분의 횟수를 리턴한다.

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        xSize = len(grid)
        ySize = len(grid[0])
        cnt = 0

        while True:
            temp = copy.deepcopy(grid)
            leftOrange = 0
            rottenOrange = 0
            for i in range(xSize):
                for j in range(ySize):
                    if grid[i][j] == 1:
                        leftOrange += 1
                    elif grid[i][j] == 2:
                        mx = [-1, 0, 1, 0]
                        my = [0, -1, 0, 1]
                        for p in range(4):
                            tx = i + mx[p]
                            ty = j + my[p]
                            if tx < 0 or tx >= xSize or ty < 0 or ty >= ySize or grid[tx][ty] == 0 or grid[tx][ty] == 2 or temp[tx][ty] == 2: continue
                            temp[tx][ty] = 2
                            rottenOrange += 1

            if rottenOrange == 0 and leftOrange != 0:
                return -1
            elif rottenOrange == 0 and leftOrange == 0:
                return cnt

            cnt += 1

            print(temp)

            grid = copy.deepcopy(temp)

2. 상한 오렌지만 관리하기

먼저 원본 배열을 순회하여 상한 오렌지들의 위치와 신선한 오렌지들의 갯수를 조사한다.

이후 상한 오렌지들에 대해 근처에 신선한 오렌지들을 상하게 하고, 새로 상한 오렌지들의 위치를 저장해 놓는다.

모든 기존의 상한 오렌지들의 근처 오렌지가 상하게 되면 새로 상한 오렌지의 갯수만큼을 신선한 오렌지 갯수에서 차감한다.

이때 신선한 오렌지 갯수가 0이면 반복한 횟수를 리턴하고, 만약 신선한 오렌지 갯수가 0이 아닌데 더이상 상할수가 없으면 -1을 리턴한다.

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        st = list()
        vertSize = len(grid)
        horiSize = len(grid[0])

        mv = [-1, 0, 1, 0]
        mh = [0, -1, 0, 1]

        freshOrange = 0

        cnt = 0

        # 초기 확인, 썩어있는 오렌지의 위치들과 멀쩡한 오렌지들의 갯수를 알아낸다.
        for v in range(vertSize):
            for h in range(horiSize):
                if grid[v][h] == 1:
                    freshOrange += 1
                elif grid[v][h] == 2:
                    st.append([v, h])

        while len(st) != 0 and freshOrange != 0:
            # 새로이 썩은 오렌지들의 위치를 저장한다.
            newRotten = []

            # 기존에 썩어있던 오렌지들을 전부 전이시킨다.
            while len(st) != 0:
                place = st.pop()
                for i in range(4):
                    tv = place[0] + mv[i]
                    th = place[1] + mh[i]
                    if tv < 0 or tv >= vertSize or th < 0 or th >= horiSize or grid[tv][th] != 1: continue
                    grid[tv][th] = 2
                    newRotten.append([tv, th])
                    freshOrange -= 1
            cnt += 1

            # 새로 썩은 오렌지들이 전이할수 있도록 해준다.
            st.extend(newRotten)

        # 오렌지를 썩일만큼 썩였는데 아직도 싱싱한게 남아있으면 더이상 진행이 불가능하기에 -1 리턴, 이외엔 cnt 리턴하면 된다.
        if freshOrange != 0:
            return -1
        else:
            return cnt