[LeetCode] 73. Set Matrix Zeroes

Problem

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

---

Solution

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean fr = false, fc = false;
        for(int i = 0; i < matrix.length; i++)
            for(int j = 0; j < matrix[0].length; j++)
                if(matrix[i][j] == 0) {
                    if(i == 0) fr = true;
                    if(j == 0) fc = true;
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
        for (int i = 1; i < matrix.length; i++)
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                matrix[i][j] = 0;
            }
        if (fr)
            for (int i = 0; i < matrix[0].length; i++)
                matrix[0][j] = 0;
        if (fc)
            for (int i = 0; i < matrix.length; i++)
                matrix[i][0] = 0;
    }
}

Explanation

• 배열 matrix속 0의 값을 가진 어느 요소로 인해 0으로 변경되는 행과 열은 다음과 같이 표시할 수 있다.
• 즉, n번째 행이 전부 0이 되어야 한다면, 첫 번째 열의 n번째 행을 0으로 표시하고, n번째 열이 전부 0이 되어야 한다면, 첫 번째 행의 n번째 열을 0으로 표시한다.

• 위의 설명을 토대로 for반복문을 작성하여 첫 번째 행과 열에 0을 표시해준다.

  for(int i = 0; i < matrix.length; i++)
    for(int j = 0; j < matrix[0].length; j++)
        if(matrix[i][j] == 0) {
            matrix[0][j] = 0;
            matrix[i][0] = 0;
        }
  

• for반복문을 작성하여 첫 번째 행과 열을 토대로 0으로 변경되어야할 행과 열들을 0으로 변경해준다.
• 첫 번째 행과 열은 위의 for반복문에서 0으로 표시가 완료되었기 때문에 for반복문의 시작은 두 번째 행과 열에서 시작하도록 한다.

  // 첫번째 행과 열을 제외하고 나머지 0으로 변환
  for (int i = 1; i < matrix.length; i++)
    for (int j = 1; j < matrix[0].length; j++) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0)
        matrix[i][j] = 0;
    }
  

• 현재는 첫 번째 행이나 열이 0으로 변경되어야 하는지에 대해서는 정보가 없다.
• 변수 fr와 fc를 작성하고 처음 작성했던 for반복문에 if조건문을 작성한다.
• 첫 번째 행이나 열이 0으로 변경되어야 한다면 true를 할당하고, 아니라면 false를 할당하도록 한다.

  // 해당 원소로 인해 0으로 변하는 행과 열을 첫번째 행과 열에 메모
  boolean fr = false, fc = false;
  for(int i = 0; i < matrix.length; i++)
    for(int j = 0; j < matrix[0].length; j++)
        if(matrix[i][j] == 0) {
            if(i == 0) fr = true;
            if(j == 0) fc = true;
            matrix[0][j] = 0;
            matrix[i][0] = 0;
        }
  

• 변수 fr과 fc의 값을 통해 첫 번째 행이나 열을 0으로 변경하도록 if조건문을 작성한다.

  // 첫번째 행 0으로 변환
  if (fr)
    for (int i = 0; i < matrix[0].length; i++)
        matrix[0][j] = 0;
  // 첫번쨰 열 0으로 변환
  if (fc)
    for (int i = 0; i < matrix.length; i++)
        matrix[i][0] = 0;