Python에서 행렬의 0 값을 기준으로 해당 행과 열을 모두 0으로 만드는 프로그램

문제 설명

2차원 숫자 행렬이 주어졌을 때, 행렬 내에 있는 각각의 0 값을 찾아서 해당 요소가 위치한 행(row)과 열(column)에 속한 모든 값을 0으로 바꾸고, 최종 행렬을 반환하는 프로그램을 작성해 보겠습니다.

예를 들어 입력 행렬에 0이 포함된 행이 있다면, 출력 결과에서 그 행 전체가 0으로 채워집니다. 마찬가지로 0이 포함된 열 역시 최종 행렬에서 해당 열 전체가 0이 됩니다.

해결 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

1. 행의 개수 n과 열의 개수 m을 구합니다.
2. n x m 크기의 결과 행렬(res)을 생성하고 모든 값을 0으로 초기화합니다.
3. 주어진 행렬의 전치 행렬(transpose)을 구합니다.
4. 각 행 i에 대해 다음을 수행합니다.
   • matrix[i]에 0이 없다면, 각 열 j를 확인합니다.
   • transpose[j](즉 j번째 열)에도 0이 없다면, res[i][j]에 원래 값 matrix[i][j]를 저장합니다.
5. 결과 행렬 res를 반환합니다.

핵심 아이디어는 결과 행렬을 먼저 0으로 채워 놓은 뒤, 0이 하나도 없는 행과 열에만 원래 값을 복원하는 방식입니다. 이렇게 하면 0을 포함하는 행이나 열은 자동으로 0으로 유지됩니다.

구현 예제

class Solution:
    def solve(self, matrix):
        n, m = len(matrix), len(matrix[0])
        res = [[0 for __ in range(m)] for _ in range(n)]
        transpose = [list(row) for row in zip(*matrix)]

        for i in range(n):
            if 0 not in matrix[i]:
                for j in range(m):
                    if 0 not in transpose[j]:
                        res[i][j] = matrix[i][j]

        return res

ob = Solution()
matrix = [
    [6, 0, 0, 6, 9],
    [4, 9, 9, 4, 8],
    [0, 8, 3, 4, 2],
    [9, 0, 7, 8, 3],
    [5, 2, 9, 6, 8]
]
print(ob.solve(matrix))

입력

matrix = [
    [6, 0, 0, 6, 9],
    [4, 9, 9, 4, 8],
    [0, 8, 3, 4, 2],
    [9, 0, 7, 8, 3],
    [5, 2, 9, 6, 8]
]

출력

[[0, 0, 0, 0, 0], [0, 0, 0, 4, 8], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 6, 8]]

결과 분석

출력 결과를 살펴보면 다음과 같습니다.

• 0행, 2행, 3행: 각 행에 0이 하나 이상 포함되어 있으므로 행 전체가 0으로 변경되었습니다.
• 1행: 행에는 0이 없지만, 0열과 1열에 0이 존재하므로 해당 위치의 값(첫 두 요소)만 0이 되고 나머지는 원래 값인 4, 8이 유지됩니다.
• 4행: 마찬가지로 0열과 1열의 영향을 받아 앞의 두 요소만 0이 되고, 6과 8은 그대로 남습니다.

이 알고리즘의 시간 복잡도는 O(n × m × (n + m))로, 각 요소마다 해당 행과 열에 0이 있는지 확인하기 때문입니다. 공간 복잡도는 전치 행렬과 결과 행렬 저장을 위해 O(n × m)입니다.