Python으로 정사각형 부분 행렬 전치만으로 한 행렬을 다른 행렬로 변환할 수 있는지 확인하는 방법

문제 이해하기

N×M 크기의 두 행렬 mat1과 mat2가 주어져 있다고 가정해 봅시다. 우리가 사용할 수 있는 연산은 단 하나, mat1 안의 임의의 정사각형 부분 행렬을 전치(transpose)하는 것입니다. 이 연산을 원하는 만큼 수행해서 mat1을 mat2로 만들 수 있는지 확인하는 것이 이 문제의 목표입니다.

예를 들어 입력이 다음과 같다고 해보겠습니다.

이 경우 출력은 True입니다. 첫 번째 행렬의 오른쪽 위 2×2 부분 행렬을 전치하면 두 번째 행렬과 완전히 같아지기 때문입니다.

핵심 아이디어: 반대각선(Anti-Diagonal)

정사각형 부분 행렬을 전치하면 원소들이 어떻게 움직일까요? 중요한 관찰은 다음과 같습니다.

• 전치 연산은 원소들을 반대각선(왼쪽 아래 → 오른쪽 위) 방향으로만 이동시킵니다.
• 따라서 어떤 부분 행렬을 몇 번이고 전치하더라도, 특정 반대각선 위에 있던 원소들은 항상 그 반대각선 위에 머무르게 됩니다.

결론적으로, 두 행렬이 서로 변환 가능하려면 모든 반대각선에 대해 mat1과 mat2의 원소 다중집합(multiset)이 동일해야 합니다. 반대각선 내에서 순서는 자유롭게 바뀔 수 있지만, 원소 구성 자체가 달라지면 절대 변환할 수 없습니다.

알고리즘 단계

• row := 행렬의 행 개수, column := 열 개수로 설정합니다.
• i를 0부터 row-1까지 반복합니다.
  • temp1, temp2라는 새 리스트를 만듭니다.
  • r := i, col := 0으로 설정한 뒤, r ≥ 0이고 col < column인 동안 mat1[r][col]과 mat2[r][col]을 각 리스트에 추가하며 r은 1씩 감소, col은 1씩 증가시켜 반대각선을 따라갑니다.
  • 두 리스트를 각각 정렬한 후, 모든 위치의 값이 일치하지 않으면 False를 반환합니다.
• j를 1부터 column-1까지 반복하며, 이번에는 (row-1, j)에서 시작하는 나머지 반대각선들에 대해 같은 과정을 수행합니다.
• 모든 반대각선 검사를 통과하면 True를 반환합니다.

구현 예제

아래 코드를 통해 더 쉽게 이해해 보겠습니다.

def solve(mat1, mat2):
    row = len(mat1)
    column = len(mat1[0])
    # 왼쪽 열에서 시작하는 반대각선 검사
    for i in range(row):
        temp1 = []
        temp2 = []
        r = i
        col = 0
        while r >= 0 and col < column:
            temp1.append(mat1[r][col])
            temp2.append(mat2[r][col])
            r -= 1
            col += 1
        temp1.sort()
        temp2.sort()
        for k in range(len(temp1)):
            if temp1[k] != temp2[k]:
                return False
    # 마지막 행에서 시작하는 나머지 반대각선 검사
    for j in range(1, column):
        temp1 = []
        temp2 = []
        r = row - 1
        col = j
        while r >= 0 and col < column:
            temp1.append(mat1[r][col])
            temp2.append(mat2[r][col])
            r -= 1
            col += 1
        temp1.sort()
        temp2.sort()
        for k in range(len(temp1)):
            if temp1[k] != temp2[k]:
                return False
    return True

mat1 = [
    [5, 6, 7],
    [1, 2, 3],
    [6, 8, 9]]
mat2 = [
    [5, 6, 2],
    [1, 7, 3],
    [6, 8, 9]]
print(solve(mat1, mat2))

입력

[
   [5, 6, 7],
   [1, 2, 3],
   [6, 8, 9]],
[
   [5, 6, 2],
   [1, 7, 3],
   [6, 8, 9]]

출력

True

복잡도 분석

• 시간 복잡도: 모든 원소를 한 번씩 방문하고 각 반대각선마다 정렬을 수행하므로 대략 O(N × M × log(max(N, M)))입니다.
• 공간 복잡도: 한 번에 하나의 반대각선만 저장하므로 O(min(N, M)) 수준의 추가 공간이 필요합니다.