leetcode medium : Rotting Oranges

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

Rotting Oranges - LeetCode

간단한 bfs 시뮬레이션 문제

 

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

        q = deque()
        s = set()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    q.append((i, j))
                    s.add((i, j))

        DX = [0, 0, 1, -1]
        DY = [-1, 1, 0, 0]

        minutes = -1

        while q:
            length = len(q)
            for _ in range(length):
                i, j = q.popleft()

                grid[i][j] = 2

                for dx, dy in zip(DX, DY):
                    nx = i + dx
                    ny = j + dy

                    if nx >= 0 and ny >= 0 and nx < len(grid) and ny < len(grid[0]):
                        if grid[nx][ny] == 1 and (nx, ny) not in s:
                            q.append((nx, ny))
                            s.add((nx, ny))

            minutes += 1

        if 1 in (item for col in grid for item in col):
            return -1
        else:
            return max(0, minutes)

 

코드는 좀 지저분하다.

 

숏코딩 챌린지를 볼까

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        row, col = len(grid), len(grid[0])
        rotting = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2}
        fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1}
        timer = 0
        while fresh:
            if not rotting: return -1
            rotting = {(i+di, j+dj) for i, j in rotting for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)] if (i+di, j+dj) in fresh}
            fresh -= rotting
            timer += 1
        return timer

ㅋㅋ 굉장히 짧다

댓글에서 이런거 그만해야된다고 일침을 가하고있다.