Logo

Rotate Image

LeetCode의 Rotate Image 문제를 함께 풀어보도록 하겠습니다.

문제

이미지를 표현하는 정사각형 행렬(n x n 2D matrix)이 주어졌을 때, 시계 방향으로 90도 회전하라. 단, 새로운 행렬을 사용하지 말고 주어진 행렬을 직접 수정해야 한다.

  • Example 1
input = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

output = [
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
  • Example 2
input = [
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
]

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

풀이 1

주어진 예제를 통해 행렬을 시계 방향으로 90도 회전할 때, 원소들의 위치가 어떻게 변화하는지 차근차근 생각해보겠습니다.

input = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

output = [
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

먼저, [0][0]에 있던 1이 어떻게 회전하는지 보겠습니다.

  • [0][0]에 있던 1은 [2][0]에 있는 7로 대체됩니다. => M[0][0] = M[2][0]
  • [2][0]에 있던 7은 [2][2]에 있는 9로 대체됩니다. => M[2][0] = M[2][2]
  • [2][2]에 있던 9은 [0][2]에 있는 3로 대체됩니다. => M[2][2] = M[0][2]
  • [0][2]에 있던 3은 [0][0]에 있는 1로 대체됩니다. => M[0][2] = M[0][0]

그 다음, [0][1]에 있던 2는 어떻게 회전하는지 보겠습니다.

  • [0][1]에 있던 2은 [1][0]에 있는 4로 대체됩니다. => M[0][1] = M[1][0]
  • [1][0]에 있던 4은 [2][1]에 있는 8로 대체됩니다. => M[1][0] = M[2][1]
  • [2][1]에 있던 8은 [1][2]에 있는 6로 대체됩니다. => M[2][1] = M[1][2]
  • [1][2]에 있던 6은 [0][1]에 있는 2로 대체됩니다. => M[1][2] = M[0][1]

그리고 [0][2]에 있던 3은 굳이 회전할 필요가 없겠죠? 그 자리에는 맨 첫 번째 단계에서 회전할 때 [0][0]에 있던 1로 대체되었기 때문입니다.

이러한 사고 과정을 통해서 우리는 다음과 같은 규칙을 도출할 수 있습니다.

  • 상단 좌측에서 우측으로 i 만큼 떨어진 값은, 하단 좌측에서 위로 i 만큼 떨어진 값으로 대체됩니다.
  • 하단 좌측에서 위로 i 만큼 떨어진 값은, 하단 우측에서 좌측으로 i 만큼 떨어진 값으로 대체됩니다.
  • 하단 우측에서 좌측으로 i 만큼 떨어진 값은, 상단 우측에서 아래로 i 만큼 떨어진 값으로 대체됩니다.
  • 상단 우측에서 아래로 i 만큼 떨어진 값은, 상단 좌측에서 우측으로 i 만큼 떨어진 값으로 대체됩니다.

만약에 더 큰 행렬이 주어진다면, 양파 껍질 벗기듯이 테두리부터 중앙으로 한 단계에서 파고 들어가면서 위 과정을 반복하면 될 것입니다. 크기가 홀수인 행렬이라면 마지막에 중앙에 하나의 원소만 남을 것이고, 크기가 짝수인 행렬이라면 마지막에 4개의 원소로 이루어진 부분 행렬이 남을 것입니다.

이 반복 알고리즘을 그대로 코드로 구현해보겠습니다. 상단 좌측에서 우측으로 i 만큼 떨어진 값이 유실되지 않도록 임시 변수에 저장해놓는 부분을 주의깊게 보시길 바랍니다.

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        top, bottom = 0, len(matrix) - 1

        while top < bottom:
            left, right = top, bottom
            for i in range(bottom - top):
                topLeft = matrix[top][left + i]
                matrix[top][left + i] = matrix[bottom - i][left]
                matrix[bottom - i][left] = matrix[bottom][right - i]
                matrix[bottom][right - i] = matrix[top + i][right]
                matrix[top + i][right] = topLeft

            top, bottom = top + 1, bottom - 1

n을 행렬의 가로/세로 크기라고 했을 때, 이 풀이는 시간 복잡도는 O(n2)이 되고 공간 복잡도는 O(1)이 됩니다. 원소들이 자리가 바뀌는 횟수는 행렬의 크기에 비례하고, 임시 변수 하나 외에는 추가 공간을 사용하지 않기 때문입니다.

풀이 2

굳이 그럴 이유는 없지만 이 문제는 재귀를 이용해서도 구현이 가능합니다. 한 번 자바로 구현을 해보았으니 참고 바랄께요.

class Solution {
    public void rotate(int[][] matrix) {
        helper(matrix,0);
    }

    private void helper(int[][] matrix, int start) {
        int size = matrix.length;
        int end = size - 1 - start;
        if (start >= end) return;
        for (int offset = start; offset < end; offset++) {
            int tmp = matrix[start][offset];
            matrix[start][offset] = matrix[size - 1 - offset][start];
            matrix[size - 1 - offset][start] = matrix[end][size - 1 - offset];
            matrix[end][size - 1 - offset] = matrix[offset][end];
            matrix[offset][end] = tmp;
        }
        helper(matrix, start + 1);
    }
}

풀이 3

앞선 풀이들은 회전을 한 번의 순회로 처리했지만, 이번에는 회전을 두 개의 더 단순한 연산으로 분해해서 접근해보겠습니다. 바로 전치(transpose)와 행 반전(reverse)입니다.

먼저 전치란 행렬의 행과 열을 서로 맞바꾸는 연산입니다. 즉, [i][j]에 있던 값과 [j][i]에 있던 값을 서로 교환하는 것인데, 결과적으로 주대각선(좌상단에서 우하단으로 이어지는 대각선)을 기준으로 행렬을 뒤집는 효과가 있습니다.

예제를 통해 직접 확인해보겠습니다.

input = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

# 전치 후 (주대각선 기준으로 뒤집힘)
transposed = [
  [1,4,7],
  [2,5,8],
  [3,6,9]
]

이렇게 전치된 행렬에서 각 행을 좌우로 반전시키면 어떻게 될까요?

# 각 행을 좌우로 반전 후
output = [
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

우리가 원하던 시계 방향 90도 회전 결과와 정확히 일치합니다!

왜 이렇게 되는지 좌표의 변화로 따져보면 더 명확해집니다. 시계 방향으로 90도 회전하면 원본의 [r][c]에 있던 값은 [c][n-1-r]로 이동해야 합니다.

  • 전치는 [r][c]를 [c][r]로 보냅니다. (행과 열을 맞바꿈)
  • 이어서 행 반전은 열 인덱스를 r에서 n-1-r로 뒤집어 [c][n-1-r]로 보냅니다.

두 연산을 합치면 [r][c] → [c][r] → [c][n-1-r]이 되어, 시계 방향 90도 회전의 목표 위치와 정확히 맞아 떨어집니다.

파이썬으로 구현해보겠습니다.

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)

        # 주대각선을 기준으로 전치(transpose)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # 각 행을 좌우로 반전
        for row in matrix:
            row.reverse()

여기서 안쪽 반복문의 j가 0이 아니라 i + 1부터 시작하는 점을 눈여겨 보시길 바랍니다. 만약 j를 0부터 시작하면 [i][j]와 [j][i] 쌍을 두 번씩 교환하게 되어 전치가 원래대로 되돌아가 버립니다. 주대각선 위쪽의 원소들만 순회해야 각 쌍을 정확히 한 번씩만 교환할 수 있습니다.

이 풀이 역시 시간 복잡도는 O(n2)이 되고 공간 복잡도는 O(1)이 됩니다. 모든 원소를 상수 번 만지고, 교환을 위한 임시 공간 외에는 추가 공간을 사용하지 않기 때문입니다. 앞선 풀이들과 점근적인 복잡도는 같지만, “행과 열을 바꾼 뒤 뒤집는다”는 두 가지 익숙한 연산의 조합이라 인덱스 계산 실수가 적고 가독성이 높다는 장점이 있습니다.