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

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

01 Matrix - LeetCode

 

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