2023.08.17 Today's Challenge

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

01 Matrix - LeetCode

생각보다 조금 어려웠던 문제.
BFS로 풀어야 함.

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        if not mat or not mat[0]:
            return []
        
        m, n = len(mat), len(mat[0])
        qu = deque()
        MAX_VALUE = m * n

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    qu.append((i, j))
                else:
                    mat[i][j] = MAX_VALUE
        
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while qu:
            row, col = qu.popleft()
            for dr, dc in dirs:
                r, c = row + dr, col + dc
                if 0 <= r < m and 0 <= c < n and mat[r][c] > mat[row][col] + 1:
                    qu.append((r,c))
                    mat[r][c] = mat[row][col] + 1
        
        return mat