[Matrix][Medium] 73. Set Matrix Zeros

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

 

Q. 주어진 m x n 행렬에서 0 인 원소가 있다면, 그 열과 행을 모두 0으로 치환하라. 

 추가 메모리를 사용하지 말아라.

 

 

 

Solution. 

 

 위 그림처럼 도중에 0이 생기면 해당 열과 행이 0으로 overwrite 된다. 

 

 추가 메모리를 사용하면, 간단하다. 하지만, 문제에서 사용할 수 없다.

 0을 만날 때 해당 행과 열을 0으로 만들면,  기존 data가 overwrite되므로, 올바를 결과를 만들 수 없다. 

 

 따라서 적절한 위치에 loop up table data를 써야 한다. 

 

 우선 추가 메모리를 쓸 수 있다면 얼마면 되겠는가 생각해 본다. 

 m x n을 통째로 다시 할당 할 수 있다면 간단하다. 

 하지만, 그렇게 까지 필요하지는 않다. 

 0으로 만들 행 데이터, 그리고 열 데이터만 있으면 될 것이다. 

 따라서 m + n 의 추가 데이터가 필요하다. 

 

 또한, 기존 행렬에서 각 첫번째 행과 열을 본다. 

 도중에 0이 나와도 해당 행(열)은 0이 되고, 자신에세 0이 나와도 해당 행(열)은 0이 됨을 알 수 있다. 

 따라서 행렬의 각 1행과 1열을 buffer로 사용한다. 

 1행의 첫번째와 1열의 첫번째가 겹치므로, 안겹치게 하나 더 할당한다.

 m + n + 1 의 데이터를 확보했다. 

 

 열의 0 데이터는 1행에 반영하고

 행의 0 데이터는 1열에 반영한다. 

 

  이를 코드로 작성해 본다. 

 

 

public void SetZeroes(int[][] matrix) 
{
    // Reflect 0 data into 1st row and col since those will be overwritten anyway.
    int x0 = 1, y0 = 1;
    for(int y = 0; y < matrix.Length; ++y)
    {
        for(int x = 0; x < matrix[0].Length; ++x)
        {
            if(matrix[y][x] == 0)
            {
                // row
                if(x == 0)  x0 = 0;
                else        matrix[0][x] = 0;

                // col
                if(y == 0)  y0 = 0;
                else        matrix[y][0] = 0;
            }
        }
    }

    // Need to reuse 1st row and col as cache.
    for(int y = 1; y < matrix.Length; ++y)
    {
        for(int x = 1; x < matrix[0].Length; ++x)
        {
            if(matrix[y][0] == 0 || matrix[0][x] == 0)
                matrix[y][x] = 0;
        }
    }

    // Use x0, y0 data.
    if(x0 == 0)     // to bottom
    {
        for(int y = 0; y < matrix.Length; ++y)
            matrix[y][0] = 0;
    }
    if(y0 == 0)     // to left.
    {
        for(int x = 0; x < matrix[0].Length; ++x)
            matrix[0][x] = 0;
    }
}

 

 코드에서 첫번째 행과 열의 0 데이터를 반영토록 각기 다른 변수를 할당하였다. 

 따라서 1열의 행과 열을 제외하면, 0 이 나오면 그 행과 열을 0으로 만들면 된다. 

 그리고 마지막으로 1열의 행과 열 데이터를 바탕으로 

 행이 0이면 그 열을 다 0 처리, 열이 0이면 그 행을 다 0 처리 한다. 

 

 

  

 

 적절한 결과를 얻었다.