(Matrix, Medium) Set Matrix Zeroes

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

처음에는 배열 모두 순회하면서 Queue에 0이 들어있는 위치를 넣고,
이 i, j 값을 기준으로 해당 행과 열을 모두 0으로 세팅하도록 코드를 짰다.

참고로 그냥 배열 두 개 더 만들어서 행,열 인덱스 boolean 체크해두고 순회하면서 체크해도 논리적으로는 동일할 듯. 코드는 더 깔끔하고.

class Solution {
    public void setZeroes(int[][] matrix) {
        
        int m = matrix.length;
        int n = matrix[0].length;

        Queue<int[]> que = new LinkedList<>();
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (matrix[i][j] == 0) {
                    que.offer(new int[] { i, j });
                }
            }
        }


        while (!que.isEmpty()) {
            int[] current = que.poll();
            setRow(current[1], matrix);
            setCol(current[0], matrix);
        }
    }

    private void setRow(int rowNum, int[][] matrix) {
        for (int i=0; i<matrix.length; i++) {
            matrix[i][rowNum] = 0;
        }
    }

    private void setCol(int colNum, int[][] matrix) {
        for (int i=0; i<matrix[0].length; i++) {
            matrix[colNum][i] = 0;
        }
    }
}

이러나 저러나 이런 방식은 O(m+n) 공간복잡도를 가지는데,
문제에서는 이것도 베스트 솔루션이 아니라고 한다.

상수 공간복잡도로 풀 수 있을까? 즉, in-place로 풀이가 가능할까?
안 떠올라서 찾아봄.

아이디어는 0행과 0열을 마커로써 활용하는 것이다.
만약 matrix[i][j] == 0이라면, matrix[i][0]과 matrix[0][j]를 0으로 마킹하는 것이다.

즉, 이 과정을 거치면 원래 요소가 0인 값을 가지고 있었던 행과 열의 시작점은 전부 0으로 마킹된다.

이후 이 마킹된 시작점을 기준으로, 아래 조건을 검사하여 해당 열과 행에 해당하는 부분을 모두 0으로 변경 처리할 수 있다.
if (matrix[i][0] == 0 || matrix[0][j] == 0)

근데 이 풀이에서 중요한 것은
시작점 행과 열에 세팅된 0이 마킹 과정에서 덮어씌워진 건지, 아님 원래 0이였던 건지 구분해야 한다는 점이다.

그래서 원본 시작점 열과 행에 0이 있는지 판단하는 플래그를 두고,
최종적으로 각각에 따른 행과 열 0 세팅 작업까지 마무리해주면 완성된다.

class Solution {
    public void setZeroes(int[][] matrix) {
        
        int m = matrix.length;
        int n = matrix[0].length;

        boolean firstRowZero = false;
        boolean firstColZero = false;

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {

                if (matrix[i][j] == 0) {
                    if (i == 0) {
                        firstRowZero = true;
                    }
                    if (j == 0) {
                        firstColZero = true;
                    }

                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (firstRowZero) {
            for (int j=0; j<n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (firstColZero) {
            for (int i=0; i<m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}