[알고리즘] 코딩인터뷰 완전분석 - 1.8 0행렬

1.8 0 행렬

M x N 행렬의 한 원소가 0일 경우, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라.

• M x N 행렬에 한 원소만이 0일 경우로 해석하여 푼 경우 - 공간복잡도 O(MN)

  #include <iostream>
  #include <utility>
  
  #define M 3
  #define N 4
  
  using namespace std;
  
  pair<int, int> get_pos(int array[][N]) {
      for (int i = 0; i < M; i++)
          for (int j = 0; j < N; j++)
              if (array[i][j] == 0)
                  return make_pair(i, j);
  }
  
  void set_zero(int array[][N], pair<int,int> pos) {
      // horizontal
      for (int i = 0; i < M; i++) 
          array[i][pos.second] = 0;
      // vertical
      for (int i = 0; i < N; i++)
          array[pos.first][i] = 0;
  }
  
  int main()
  {
      int array[M][N] = { {1,1,1,1}, {1,0,1,1}, {1,1,1,1} };
      pair<int, int> pos;
  
      pos = get_pos(array);
      set_zero(array, pos);
  }

  • M x N 이라서 0인 놈을 찾으려면 O(MN)이 될 수 밖에 없다.
  • 만일 행렬에 0이 여러개 있다면, vector안에 값이 0인 행렬의 좌표를 pair에 넣어 vector요소를 하나씩 돌며 관련된 행과 열을 0으로 수정하려했다.

---

• 행렬에 오직 하나가 0인 경우가 아닐 경우(문제에서 원하는 풀이) - 공간복잡도 O(1)

  #include <iostream>
  
  #define M 4
  #define N 5
  
  using namespace std;
  
  void nullify_row(int matrix[][N], int row) {
      for (int j = 0; j < N; j++)
          matrix[row][j] = 0;
  }
  
  void nullify_col(int matrix[][N], int col) {
      for (int i = 0; i < M; i++)
          matrix[i][col] = 0;
  }
  
  void set_zero(int matrix[][N]) {
      bool row_has_zero = false;
      bool col_has_zero = false;
  
      // is there '0' on first row?
      for (int j = 0; j < N; j++) {
          if (matrix[0][j] == 0) {
              row_has_zero = true;
              break;
          }
      }
      // is there '0' on first columm?
      for (int i = 0; i < M; i++) {
          if (matrix[i][0] == 0) {
              col_has_zero = true;
              break;
          }
      }
      // check the rest of the array has '0'
      for (int i = 1; i < M; i++) {
          for (int j = 1; j < N; j++) {
              if (matrix[i][j] == 0) {
                  matrix[i][0] = 0;
                  matrix[0][j] = 0;
              }
          }
      }
      // use 1st columm to change the row to '0'
      for (int i = 1; i < M; i++) {
          if (matrix[i][0] == 0) 
              nullify_row(matrix, i);
      }
      // use 1st row to change the columm to '0'
      for (int j = 1; j < N; j++) {
          if (matrix[0][j] == 0)
              nullify_col(matrix, j);
      }
      // change the 1st row to '0'
      if (row_has_zero) 
          nullify_row(matrix, 0);
      // change the 1st columm to '0'
      if (col_has_zero)
          nullify_col(matrix, 0);
  }
  
  int main()
  {
      int matrix[M][N] = { {1,1,1,1,0}, {1,1,1,1,1}, {0,1,1,1,1}, {1,1,1,1,1} };
  
      set_zero(matrix);
  }

  • 첫 번째 행을 row 배열로, 첫 번째 열을 columm 배열로 사용하면 공간 효율을 O(1)로 낮출 수 있다.

1. 첫번째 행과 첫번째 열 안에 0이 있는지 검사한 다음, 있다면 `row_has_zero`와 `col_has_zero` 변수를 참으로 설정한다(나중에 첫번째 행과 열을 0으로 만드는 작업을 할 것임).
2. 배열의 나머지 부분을 순회하면서 값이 0인 `matrix[i][j]`를 만날 때마다 `matrix[0][j]`, `matrix[i][0]`를 0으로 설정한다.
3. 행렬의 나머지 부분을 순회하면서 `matrix[i][0]`이 0인 모든 행 `i`를 0으로 만든다.
4. 행렬의 나머지 부분을 순회하면서 `matrix[0][j]`이 0인 모든 열 `j`를 0으로 만든다.
5. 맨 처음에 설정한 값에 따라 필요한 경우에 첫번째 행과 첫번째 열을 0으로 만든다.