[Algorithm] 2차원 배열 회전

알고리즘, 코딩 테스트 문제를 풀다보면 정방형 2차원 배열을 회전시켜 방법을 찾아가는 문제들이 종종 보인다. 대표적으로는 카카오의 2020 블라인드 채용 문제3 이 있다.

배열을 회전시키는 문제의 경우, 계속 반복적으로 배열의 회전을 요하기 때문에 함수로 만들어놓고 활용하면 간결하고, 사용하기도 쉽다.

회전의 경우 90도, 180도, 270도 회전이 있다. '180도 할거면, 90도 2번 하면 되는 것 아니야?' 라는 질문도 있을 수 있겠다. 그것도 당연히 맞다. 하지만 단순히 90도의 회전을 요구하는 것이 아닌 많은 양의 180도 회전 또는 270도 회전을 해야할 상황이라고 하자. 180도 회전 연산을 1번 하는 상황에서는 90도 회전 연산을 2번 해야하기에 앞 상황에서 치자면 연산이 2~3배는 늘어나는 상황인 것이다. 더욱이 알고리즘, 코딩 테스트에서는 연산 시간을 줄이고자 노력해야하므로, 180도 및 270도 회전도 알아두면 좋을 것이라 생각한다.

90도 회전

다음과 같이 정방형 2차원 배열이 존재할 때, 90도 회전을 수행하면 오른쪽의 행렬처럼 될 것이다. 여기서 1, 2, 3에만 주목해서 식을 구해보자. 먼저, 단순히 생각이 안된다면 행과 열 index(번호)를 참조해서 규칙을 찾아내보자.

(0, 0), (0, 1), (0, 2) -> (0, 2), (1, 2), (2, 2)

규칙을 찾아내보면, 다음과 같다.

• 회전 후의 행 index는 기존 열 index가 된다.
• 회전 후의 열 index는 기존 행, 열 마지막 index(2)에서 기존 행 index(0)을 뺀 값이 된다.

그럼 이걸 함수로 작성해보자

def rotate_matrix_90(matrix):
    N = len(matrix) # 행 및 열 길이
    res = [[0] * N for _ in range(N)] # 결과를 담아둘 행렬 정의 

    for row in range(N):
        for col in range(N):
            res[col][N-1-row] = matrix[row][col] # 행, 열의 마지막 index는 N-1
    return res

앞서 말한 규칙은 res[col][N-1-row] = matrix[row][col] 으로 작성할 수 있다. col은 그대로 새로운 행이 되며, 행, 열의 마지막 index는 N-1 이므로 N-1-row가 새로운 열이 된다.

180도 회전, 270도 회전도 이와 같은 원리로 쉽게 찾아낼 수 있다.

180도 회전

90도 회전과 마찬가지로 다음의 예제를 두고 규칙을 찾아보도록 하자.

(0, 0), (0, 1), (0, 2) -> (2, 2), (2, 1), (2, 0)

규칙을 찾아내보면, 다음과 같다.

• 회전 후의 행 index는 기존 행, 열 마지막 index(2)에서 기존 행 index을 뺀 값이 된다.
• 회전 후의 열 index는 기존 행, 열 마지막 index(2)에서 기존 열 index을 뺀 값이 된다.

함수로 작성해보면

def rotate_matrix_180(matrix):
    N = len(matrix) # 행 및 열 길이
    res = [[0] * N for _ in range(N)] # 결과를 담아둘 행렬 정의 

    for row in range(N):
        for col in range(N):
            res[N-1-row][N-1-col] = matrix[row][col]
    return res

270도 회전

(0, 0), (0, 1), (0, 2) -> (2, 0), (1, 0), (0, 0)

규칙을 찾아내보면, 다음과 같다.

• 회전 후의 행 index는 기존 행, 열 마지막 index(2)에서 기존 열 index을 뺀 값이 된다.
• 회전 후의 열 index는 기존 행 index가 된다.

함수로 작성해보면

def rotate_matrix_270(matrix):
    N = len(matrix) # 행 및 열 길이
    res = [[0] * N for _ in range(N)] # 결과를 담아둘 행렬 정의 

    for row in range(N):
        for col in range(N):
            res[N-1-col][row] = matrix[row][col]
    return res

끝으로

이렇게 정방형 2차원 행렬의 회전을 알아보았다 !
매우 단순하지만, 사실 마음이 급해지는 시험 상황에서 이걸 생각하면 의외로 연산이 꼬일 수도 있다고 생각한다. 그래서 미리 알아두고 외워두는 것을 추천하지만, 만약 생각이 안난다면 행과 열 번호를 바꾸거나 행과 열 크기에서 기존 행, 열 번호를 빼는 행동으로 회전을 시킬 수 있다는 것만이라도 머릿 속에 넣어두고 시험을 보면 좋을 것 같다.