[Algorithm] Rotate Matrix

Rotate Matrix

구현문제 중엔 Rotate Matrix 류가 있습니다. NxM 행렬을 주고 이 행렬을 90도 방향으로 회전시키게 하는 문제들입니다.

구현 시 팁, 주의점

테두리 단위로 회전을 시킵다. 바깥 테두리부터 회전을 시켜 내부의 테두리들을 재귀적으로 호출하고 테두리가 1이나 0인 경우가 기저케이스가 됩니다.

먼저 Swap 기능을 구현할 때처럼 덮어씌워짐에 의해 정보유실이 일어날 수 있어 추가적인 공간에 한 행을 저장시킵니다.
그 다음 문제의 요구에 맞게 값들을 이동시켜줍니다. 이 때 인덱스 계산이 꽤 복잡할 수 있습니다.
팁을 드리자면 시작좌표(y, x), 행렬길이가 필요합니다.

값들의 이동 순서는 아래 이미지에서 볼 수 있듯 빨강부터 시작해 마지막에 주황이 처리될 수 있도록 해야합니다.
이미지에서도 볼 수 있듯 빨강의 시작점이 주황의 도착점이라 빨강의 정보를 유실시킵니다.

구현코드

Leetcode 1886번의 해답코드입니다. (nxn 행렬을 대상으로 90도 회전을 시키는 문제입니다.)

class Solution:
    def findRotation(self, matrix: List[List[int]], target: List[List[int]]) -> bool:
        def checkEquality(mat1, mat2):
            n = len(mat1)
            for i in range(n):
                for j in range(n):
                    if mat1[i][j] != mat2[i][j]:
                        return False
            return True

        def rotate90Degrees(square, start, size):
            if size <= 1:
                return
            start_y, start_x = start
            temp = [square[start_y][start_x + i] for i in range(size)]
            for i in range(size):
                square[start_y][start_x + size - 1 - i] = square[start_y + i][start_x]
            for i in range(size):
                square[start_y + i][start_x] = square[start_y + size - 1][start_x + i]
            for i in range(size):
                square[start_y + size - 1][start_x + i] = square[start_y + size - 1 - i][start_x + size - 1]
            for i in range(size):
                square[start_y + size - 1 - i][start_x + size - 1] = temp[size - 1 - i]
            rotate90Degrees(square, (start_y + 1, start_x + 1), size - 2)

        for _ in range(4):
            rotate90Degrees(matrix, (0, 0), len(matrix))
            if checkEquality(matrix, target):
                return True
        return False

Python 의 내장함수를 사용한 간단한 방법

class Solution:
    def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
        for _ in range(4): 
            if mat == target: return True
            mat = [list(x) for x in zip(*mat[::-1])]
        return False 

조금 설명을 하자면 아래와 같습니다.

mat = [list(x) for x in zip(*mat[::-1])]

다음과 같은 행렬이 있습니다.

1 2 3
4 5 6
7 8 9

mat[::-1]는 행렬을 역순으로 뒤집습니다. (행을 reverse), 시간복잡도는 O(n)
7 8 9
4 5 6
1 2 3

zip(*mat[::-1])는 역순으로 뒤집은 후, 각 행의 요소를 열로 묶어서 새로운 행렬을 생성합니다. 이 과정은 90도 회전과 동일합니다.
zip 함수의 동작은 다음과 같습니다. 시간복잡도 O(n)

list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']

zipped = zip(list1, list2)
print(list(zipped))  # [(1, 'a'), (2, 'b'), (3, 'c')]

즉, 열끼리 묶어줍니다.

* 연산자는 2차원 배열에서 내부배열을 퍼뜨려주는 역할입니다. 현재 예시에선 2차원 배열을 3개의 1차원 배열로 퍼뜨립니다.

마지막으로, list(x)를 통해 zip의 결과를 리스트로 변환합니다.
7 4 1
8 5 2
9 6 3

완성입니다.