542. 01 Matrix

https://leetcode.com/problems/01-matrix/description/?envType=problem-list-v2&envId=breadth-first-search

 

 

 

 

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

 

1에서부터 가장 가까운 0의 값을 배열에 저장해주면 되는 문제였다.

 

• 배열이 0이라면 큐에 삽입
  • 1이라면, -1로 초기화를 해준다 (거리 값 초기화)
• 배열이 0인 곳에서부터 탐색을 하면서 거리가 -1인 곳을 계속해서 갱신해나가면 되는 문제였다. 

 

정답 코드

class Solution {
    int n, m;
    int [] dx = {1,0,-1,0};
    int [] dy = {0,1,0,-1};
    public int[][] updateMatrix(int[][] mat) {
        n = mat.length;
        m = mat[0].length;
        Queue<int []> q = new LinkedList<>();
        boolean [][] visited = new boolean[n][m];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (mat[i][j] == 0) q.add(new int[]{i,j});
                else mat[i][j] = -1; // -1로 초기화 
            }
        }

        while(!q.isEmpty()) {
            int [] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            visited[x][y] = true;

            for(int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (visited[nx][ny] || mat[nx][ny] == 0) continue;
                mat[nx][ny] = mat[x][y] + 1;
                visited[nx][ny] = true;
                q.add(new int[]{nx,ny});
            }
        }
        return mat;
    }
}