메인 내용으로 이동

# 0542 01 Matrix

Solved at: 2023-01-30

01 Matrix - LeetCode

## Question​

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.

## Solution​

class Solution {    func updateMatrix(_ matrix: Int) -> Int {        // fill the zeros first        var mat = matrix        var queue: [(Int, Int)] = []        for (i, row) in mat.enumerated() {            for (j, col) in row.enumerated() {                if mat[i][j] == 0 {                    queue.append((i, j))                }                mat[i][j] = -1            }        }        var level = 0        while !queue.isEmpty {            let count = queue.count            for i in 0..<count {                let (r, c) = queue.remove(at: 0)                if mat[r][c] == -1 {                    mat[r][c] = level                }                if r > 0 && mat[r-1][c] == -1 {                    queue.append((r-1, c))                }                if c > 0 && mat[r][c-1] == -1 {                    queue.append((r, c-1))                }                if r < mat.count - 1 && mat[r+1][c] == -1 {                    queue.append((r+1, c))                }                if c < mat[0].count - 1 && mat[r][c+1] == -1 {                    queue.append((r, c+1))                }            }            level += 1        }        return mat    }}

## Results​

• Time taken: 11 m 43 s
• Runtime 1856 ms, Beats 10.39%
• Memory 15.5 MB, Beats 83.12%

## Complexity Analysis​

• Time: $O(N \times c)$
• Space: $O(N \times c)$

Where $c$ is the cost — the number of iterations in which "BFS clear" operation will run.