[LeetCode] 73. Set Matrix Zeroes - 구현(Implementation) JAVA

https://leetcode.com/problems/set-matrix-zeroes/description/

코드설명

구현(Implementation) 을 활용합니다.

 

문제에서 In-Place로 구현하라는 말이 있었지만, Queue를 활용하여 자료구조를 활용했습니다. 

문제에서 유의할사항은, Queue에 0을 넣을떄, 이후에 0으로 바꾸어야한다는 점입니다.

그렇게 해야만, 다음 칸을 검사하면서 0이 바뀐 값을 검색하는 것이 아니라, 원래 값을 기준으로 업데이트합니다.

코드

정답코드1입니다.

class Solution {
    //in-place 방식은 모르겠음.
    //큐에 데이터를 먼저 넣고, 갱신은 안해야 데이터 오염이 없습니다.
    static int[][] dir = new int[][] { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static boolean[][] visited;
    public void setZeroes(int[][] matrix) {
        Queue<int[]> q = new LinkedList<>();
        int N = matrix.length;
        int M = matrix[0].length;
        visited = new boolean[N][M];
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(matrix[i][j] != 0) continue;
                for(int k = 0; k < 4; k++){
                    int nr = i + dir[k][0];
                    int nc = j + dir[k][1];
                    if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                    q.offer(new int[]{nr, nc, k});
                }
            }
        }

        while(!q.isEmpty()){
            int[] temp = q.poll();
            int r = temp[0];
            int c = temp[1];
            int dirIdx = temp[2];
            matrix[r][c] = 0;

            int nr = r + dir[dirIdx][0];
            int nc = c + dir[dirIdx][1];

            if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            matrix[nr][nc] = 0;
            q.offer(new int[]{nr, nc, dirIdx});
        }
        
    }
}