LeetCode: 73번 (Set Matrix Zeroes) [JAVA]

문제 링크

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

Set Matrix Zeroes - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 matrix 행과 열 길이만큼의 boolean 배열 row, col 생성
2. 이중 for문을 통해 전체 matrix 배열을 돌며 해당 위치의 값에 따라 동작
   1. 만약 해당 값이 0이라면 해당 행과 열을 boolean 배열에 표시 후 해당 위치로부터 동일 행에 한해 그 앞의 모든 열 속의 요소 값을 0으로 초기화하고, 비슷하게 동일 열에 한해 그 앞의 모든 행 속의 요소 값들을 0으로 초기화
   2. 해당 값이 0이 아니라면 해당 행과 열 인덱스를 가지고 앞선 boolean 배열에 판단하여 앞선 과정에서 0으로 초기화해야 할 위치인지 판단 후 0으로 초기화

 문제 속에서 개인적인 판단으로는 적어도 한 번은 주어진 matrix를 모두 탐색해야 하기 때문에, 그 이후 과정에서 배열 요소를 바꿔야하는 과정에서 최대한 중복 방문을 줄이는 방법으로 코드를 작성했다. 기본적인 이중 for문을 통해 탐색을 진행할 때 특정 위치에 있어 해당 위치보다 행이 더 앞에 있거나 열이 더 앞에 있는 경우는 이미 탐색이 완료된 상태이기 때문에 그 값을 수정한다고 이후 탐색에 영향을 주진 않는다. 그러기 때문에 문제에선 0이 주어진 곳에서 모든 행과 열 속 요소들을 0으로 바꿔야 하지만, 만약 그렇다고 뒤의 행이나 열 속 요소들의 값을 0으로 바꾸게 되면 이후 탐색 시 해당 위치가 0이라고 판단되어 오류가 발생된다.

 그러기 때문에 우선 주어진 matrix 행과 열 길이만큼의 boolean 배열 row, col를 생성하고, 이중 for문 탐색을 통해 각 요소의 값을 파악한다. 이 때 각 요소의 값을 확인하면서, 그 값에 따라 동작을 다르게 실행한다. 만약 0인 경우 해당 행과 열을 모두 0으로 바꾸어야 하기 때문에 우선 해당 행과 열을 boolean 배열에 추가적으로 표시를 진행하고, 해당 위치보다 이전 열들의 요소를 0으로 바꾸고 동일하게 이전 행들의 요소를 0으로 바꾼다. 만약 0이 아니라면 앞선 탐색을 하며 해당 행 또는 열 인덱스가 모두 0으로 바꾸어야하는 부분일 수도 있기 때문에, 앞선 boolean 배열로 해당 부분을 확인하고 맞다면 값을 0으로 초기화하고 아니면 다음 탐색으로 넘어간다.

 

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean[] row = new boolean[matrix.length], col = new boolean[matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {//0이라면
                    row[i] = true;//해당 행 표시
                    col[j] = true;//해당 열 표시

                    for (int k = j - 1; k >= 0; k--) {//그 이전 열 0표시
                        matrix[i][k] = 0;
                    }

                    for (int k = i - 1; k >= 0; k--) {//그 이전 행 0 표시
                        matrix[k][j] = 0;
                    }
                } else {
                    if (row[i] || col[j]) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    }
}

결과