Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 행렬의 행과 열을 0으로 설정하기 (Set Matrix Zeroes)

문제 개요

행렬(matrix)이 하나 주어졌다고 가정해 보겠습니다. 이 행렬에서 어떤 요소가 0이라면, 그 요소가 속한 행과 열 전체를 모두 0으로 만들어야 합니다. 이때 변환은 제자리(in-place) 방식으로 수행되어야 하므로, 추가적인 행렬을 새로 생성하지 않고 원본 행렬을 직접 수정해야 합니다.

예를 들어 다음과 같은 행렬이 입력으로 주어진다면 −

101
111
111

결과는 다음과 같습니다 −

000
101
101

(0, 1) 위치의 요소가 0이었기 때문에 첫 번째 행 전체와 두 번째 열 전체가 함께 0으로 변경된 것을 확인할 수 있습니다.

알고리즘 접근 방식

이 문제를 O(1)의 추가 공간으로 해결하기 위해 첫 번째 행과 첫 번째 열을 마커(marker)로 활용합니다. 내부 영역(i ≥ 1, j ≥ 1)에서 0이 발견되면, 해당 정보를 각각 첫 번째 열(mat[i][0])과 첫 번째 행(mat[0][j])에 기록해 둡니다. 이후 마커 정보를 바탕으로 내부 영역을 먼저 0으로 채우고, 마지막에 첫 번째 행과 열을 처리하는 순서로 진행됩니다.

단계별 풀이

  • n := 행의 개수, m := 열의 개수로 설정하고, flag := false로 초기화합니다.
  • 만약 mat[0, 0] = 0이라면 flag := true로 설정합니다. (첫 번째 행과 열이 모두 0이 되어야 함을 의미)
  • row := false, col := false로 초기화합니다.
  • i를 1부터 n-1까지 반복하면서 mat[i, 0] = 0인 경우 col := True로 설정하고 반복문을 종료합니다.
  • i를 1부터 m-1까지 반복하면서 mat[0, i] = 0인 경우 row := True로 설정하고 반복문을 종료합니다.
  • i를 1부터 n-1까지, j를 1부터 m-1까지 이중 반복하면서 mat[i, j] = 0이면 mat[i, 0] = 0과 mat[0, j] = 0으로 설정하여 마커를 기록합니다.
  • 다시 i를 1부터 n-1까지, j를 1부터 m-1까지 이중 반복하면서 mat[i, 0] = 0 또는 mat[0, j] = 0이면 mat[i, j] = 0으로 설정합니다.
  • flag가 설정되어 있는 경우(즉, mat[0, 0]이 원래 0이었던 경우):
    • i를 0부터 n-1까지 반복하며 mat[i, 0] := 0으로 설정합니다.
    • i를 0부터 m-1까지 반복하며 mat[0, i] := 0으로 설정합니다.
  • 그렇지 않은 경우:
    • col이 설정되어 있으면, i를 0부터 n-1까지 반복하며 mat[i, 0] := 0으로 설정합니다.
    • row가 설정되어 있으면, i를 0부터 m-1까지 반복하며 mat[0, i] := 0으로 설정합니다.

구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다 −

class Solution(object):
   def setZeroes(self, matrix):
      n = len(matrix)
      m = len(matrix[0])
      flag = False
      if matrix[0][0] == 0:
         flag = True
         row = False
         column = False
      for i in range(1,n):
         if matrix[i][0] == 0:
            column = True
            break
      for i in range(1,m):
         if matrix[0][i] == 0:
            row = True
            break
      for i in range(1,n):
         for j in range(1,m):
            if matrix[i][j] == 0:
               matrix[0][j] = 0
               matrix[i][0]=0
      for i in range(1,n):
         for j in range(1,m):
            if not matrix[i][0] or not matrix[0][j]:
               matrix[i][j] = 0
      if flag:
         for i in range(n):
            matrix[i][0] = 0
         for i in range(m):
            matrix[0][i]=0
      else:
         if column:
            for i in range(n):
               matrix[i][0]=0
         if row:
            for i in range(m):
               matrix[0][i]=0
      return matrix
ob1 = Solution()
print(ob1.setZeroes([[1,0,1],[1,1,1],[1,1,1]]))

입력

[[1,0,1],[1,1,1],[1,1,1]]

출력

[[0, 0, 0], [1, 0, 1], [1, 0, 1]]

복잡도 분석

시간 복잡도: O(n × m) — 행렬의 모든 요소를 몇 차례 순회하므로 행렬의 크기에 비례합니다.
공간 복잡도: O(1) — 별도의 추가 저장 공간 없이 행렬 자체의 첫 번째 행과 열을 마커로 활용하기 때문입니다.