🎵542. 01 Matrix java

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

01 Matrix - LeetCode

나의 경우 dfs로만 접근했었는데, 4가지 방향에 대해 우선적으로 칼큘레이션이 되었다가

그 다음 방향으로 뻗어서 계산을 해야 문제에서 의도한 답이 나올 수 있으므로 bfs 즉, q를 반드시 사용해야했다.

 

q를 이용한 문법이 아직 익숙하지 않아 아래 코드를 참고하여 다시 풀어볼 예정!

 

class Solution {
    private final int[][] DIRECTIONS = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};

    public int[][] updateMatrix(int[][] mat) {

        int m = mat.length;
        int n = mat[0].length;

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j]==0){  // 0부터의 거리므로 시작점 0을 큐에 넣어줌
                    q.offer(new int[]{i,j});
                }else{ // marking 아직 거리가 표기되지 않은 것을 대상으로 큐 확장을 위함
                    mat[i][j] = -1;
                }
            }
        }

        while(!q.isEmpty()){ // 0부터 꺼내가며 BFS로 확장해 나감

            int[] curr = q.poll();

            for(int[] d:DIRECTIONS){
                int nr = curr[0]+d[0];
                int nc = curr[1]+d[1];
                if( nr < 0 || nc < 0 || nr >= mat.length || nc >= mat[0].length || mat[nr][nc] != -1) continue; // -1로 표기된것만 대상
                mat[nr][nc] = mat[curr[0]][curr[1]]+1; // 이전거리를 다음큐에 가져올수가 없으니 먼저 데이터를 넣어줌!
                q.offer(new int[]{nr,nc});
            }
        }
        
        return mat;
    }

}

참고 : https://ifuwanna.tistory.com/329