leetcode medium : 01 Matrix (Grind 75 Graph 문제 2)

띠리링구 2023. 2. 23. 01:06

https://leetcode.com/problems/01-matrix/description/

01 Matrix - LeetCode

01 Matrix - Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Example 1: [https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg] Input: mat = [[0,0,0],[0,1,0],[0,0,

leetcode.com

grind 75에서 난이도순으로 나열된 graph 문제 중에 두 번째인데 벌써 어렵다.

잠을 2시간밖에 못자고 회식을 5시간씩 달리고 와서 머리가 안돌아가서 그런가..?

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        q = deque()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    q.append((i, j))
                else:
                    matrix[i][j] = -1

        while q:
            x, y = q.popleft()
            for r, c in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                newX, newY = x+r, y+c
                if 0 <= newX < len(matrix) and 0 <= newY < len(matrix[0]) and matrix[newX][newY] == -1:
                    matrix[newX][newY] = matrix[x][y] + 1
                    q.append((newX, newY))
        return matrix