박종훈 알고리즘 블로그

행렬 90도 회전

행렬 회전: 이미지를 표현하는 N x N 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때, 이미지를 90도 회전시키는 메서드를 작성하라. 행렬을 추가로 사용하지 않고서도 할 수 있겠는가?

  • N x N 행렬
  • 90도 회전
  • 행렬 추가 사용 금지

위 조건들을 기반으로 생각을 해보자.

일단 행렬 추가 사용 금지 라고 했기 때문에 swap 하는 방식으로 처리가 되야 할 것이다.

문제를 간략화해서 다음과 같이 생각해보자.
아래와 같은 행렬이 있다고 하자.

[
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]

이 행렬을 90도 회전하면 다음과 같을 것이다.

[
    [13, 9, 5, 1],
    [14, 10, 6, 2],
    [15, 11, 7, 3],
    [16, 12, 8, 4]
]

첫 줄을 보자.
[0,0], [0,1], [0,2], [0,3] 이
[0,3], [1,3], [2,3], [3,3] 으로
되었다.

두번째 줄을 보자.
[1,0], [1,1], [1,2], [1,3] 이
[0,2], [1,2], [2,2], [3,2] 으로
되었다.

세번째 줄을 보자.
[2,0], [2,1], [2,2], [2,3] 이
[0,1], [1,1], [2,1], [3,1] 으로
되었다.

마지막 줄을 보자.
[3,0], [3,1], [3,2], [3,3] 이
[0,0], [1,0], [2,0], [3,0] 으로
되었다.

규칙을 찾아보자.
행렬의 크기를 N (여기서는 4), 첫번째 값을 i, 두번째 값을 j 라고 하자.

[i, j] → [j, N - i -1]

이다.


일단 규칙은 찾았는데 스왑은 어떻게 시킬까?

Matrix에서의 swap 도 일반적인 경우와 마찬가지로 임시 저장공간을 이용하여 진행한다.

코드는 아래와 같다.

def rotate_matrix(matrix):
    n = len(matrix)

    for layer in range(n // 2):
        first = layer
        last = n - 1 - layer

        for i in range(first, last):
            offset = i - first

            # 임시 저장
            top = matrix[first][i]

            # 왼쪽 -> 위쪽
            matrix[first][i] = matrix[last - offset][first]

            # 아래쪽 -> 왼쪽
            matrix[last - offset][first] = matrix[last][last - offset]

            # 오른쪽 -> 아래쪽
            matrix[last][last - offset] = matrix[i][last]

            # 위쪽 -> 오른쪽
            matrix[i][last] = top

# 예시 입력 행렬
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]

rotate_matrix(matrix)

# 회전 후 행렬 출력
for row in matrix:
    print(row)

바깥쪽 부터 시계 방향으로 돌린다고 생각하면 된다.
궁금하면 first, last, i, offset이 어떻게 바뀌는지 찍어보면서 동작시켜보면 좋다.


// 연산

python 에서 // 연산은 /와 동일하게 나눗셈 연산을 처리하지만 float이 아닌 int를 반환한다.

categories: 스터디-알고리즘

tags: swap , matrix , rotate