[LeetCode] 542. 01 Matrix - BFS

문제 링크 : https://leetcode.com/problems/01-matrix/

01 Matrix - LeetCode

 

01 Matrix - LeetCode

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]

Note

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

---

풀이

1. 0이 아닌 좌표를 발견했을 때 0이 해당 지점에서 얼마나 떨어져있는지를 BFS를 통해 찾으면 되는 문제!

from collections import deque
class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:

        def find_nearest0(i, j, matrix, level):

            q = deque()
            q.append([level, [i, j]]) # q에 레벨, (i, j) 좌표가 들어간다

            n_c = [-1, 0, 1, 0]
            n_r = [0, -1, 0, 1]
            res = 0

            while q:
                l, a = q.popleft()
                ni, nj = a[0], a[1]

                if matrix[ni][nj] == 0:
                    res = l
                    break

                for i in range(4):
                    next_c = ni + n_c[i]
                    next_r = nj + n_r[i]
                    if next_c >= 0 and next_c < len(matrix) and next_r >= 0 and next_r < len(matrix[0]):
                        q.append([l+1, [next_c, next_r]])
            return res


        res = matrix
        for i in range(len(res)):
            for j in range(len(res[i])):
                if res[i][j] != 0:
                    res[i][j] = find_nearest0(i, j, matrix, 0)
        return res