[LeetCode] 542. 01 Matrix

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

01 Matrix - LeetCode

 

문제 유형 : BFS / DFS (+Multi-Source BFS, 다중 출발점 BFS)

문제 난이도 : Medium

 

문제

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.

 

m * n의 mat라는 이진 매트릭스(0또는 1의 값을 가지는 2차원 배열)가 주어진다. mat의 숫자들이 가장 가까운0까지의 거리를 구하시오.

칸마다의 거리는 1이다.

 

풀이

m x n 크기의 2차원 배열 table을 만들어서, 모든 값을 -1로 초기화한다.

이중 반복문을 사용하여 전체 배열을 탐색하면서, mat의 값이 0인 경우 table의 해당 위치 값을 0으로 업데이트하고, 그 위치를 큐에 넣는다.

큐에서 위치를 하나씩 꺼내면서, 해당 위치에서 상하좌우 방향으로 인접한 위치를 확인한다. 만약 인접한 위치의 mat 값이 1이고 table 값이 -1이면, 현재 위치의 table 값에 1을 더한 값을 해당 위치의 table에 업데이트하고, 그 위치를 다시 큐에 넣는다.

이 과정을 통해 각 위치에서 가장 가까운 0까지의 거리를 알 수 있다.

큐에 더 이상 요소가 없을 때까지 이 과정을 계속 반복한다.

최종적으로 완성된 테이블을 반환한다.

 

코드

C++

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        queue<vector<int>> q;

        vector<vector<int>> table (m, vector<int>(n, -1));

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(mat[i][j] == 0) {
                    table[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        vector<int> dx = {1, -1, 0, 0};
        vector<int> dy = {0, 0, 1, -1};

        while(!q.empty()) {
            int a = q.front()[0];
            int b = q.front()[1];
            q.pop();

            for (int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];

                if (0 <= x && x < m && 0 <= y && y < n && table[x][y] == -1 && mat[x][y] == 1) {
                    table[x][y] = table[a][b] + 1;
                    q.push({x, y});
                }
            }
        }
        return table;
    }

};

 

Python3

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])

        q = deque()
        table = [n * [-1] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    table[i][j] = 0
                    q.append((i, j))

        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]

        while q:
            a, b = q.popleft()

            for i in range(4):
                x = a + dx[i]
                y = b + dy[i]

                if(0<=x<m and 0<=y<n and mat[x][y] == 1 and table[x][y] == -1):
                    table[x][y] = table[a][b] + 1
                    q.append((x, y))

        
        return table

 

Java

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;

        int[][] table = new int[m][n];

        Queue<int[]> q = new LinkedList<>();

        for(int [] row: table) {
            Arrays.fill(row, -1);
        }

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(mat[i][j] == 0) {
                    table[i][j] = 0;
                    q.add(new int[] {i, j});
                }
            }
        }

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while(!q.isEmpty()) {
            int[] curr = q.poll();
            int a = curr[0], b = curr[1];

            for(int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];

                if(x >= 0 && x < m && y >= 0 && y < n && mat[x][y] == 1 & table[x][y] == -1) {
                    table[x][y] = table[a][b] + 1;
                    q.add(new int[] {x, y});
                }
            }
        }

        return table;
    }
}