[Python] 2차원 배열 90도 회전 알고리즘

코딩테스트 2020 KAKAO 신입 공채 를 풀다보니 2차원 배열의 90도 회전을 요구하는 문제가 있었다.

파이썬에서 2차원 리스트를 다룰 때 종종 사용되는 개념이므로 코드공식에 적어두고 필요할 때마다 꺼내봐야겠다.

 

 

그 전에 회전 알고리즘 원리를 먼저 파악해보자.

해당 2020 카카오 문제를 풀면서 2차원 배열 회전을 처음 맞닥뜨렸다면 절대 제시간 내에 풀지 못했을 것이다..

 

보다 이해하기 쉽게 정리해봤다. 시계방향으로 90도 회전할 때, 회전 후의 행과 열 값을 알아야 한다.

2차원 배열이 회전할 때는 일정한 규칙이 있다. 90도 회전할 때의 위치를 모두 연결해보면 일정한 사이클이 있다.

사이클이 생긴다는 것은 요소의 합이 N일 가능성이 있다. (이때 N은 사각형의 크기)

그래서 나온 공식이 사진의 1번, 2번이다.

1. 회전 후의 행 번호 = 회전 전의 열 번호
2. 회전 후의 열 번호 = N - 1 - 회전 전의 행 번호

 

 

 

코드로 나타내면 아래와 같다.

 

90도 회전

def rotate_2d(list_2d):
    n = len(list_2d) # 행 길이 계산
    m = len(list_2d[0]) # 열 길이 계산
    new = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            new[j][n-i-1] = list_2d[i][j]
    return new

 

180도 회전

90도 회전을 두 번 하는 것이니, [j] 열 입장에서도 사이클이 생긴다.

def rotate_2d(list_2d):
    n = len(list_2d) # 행 길이 계산
    m = len(list_2d[0]) # 열 길이 계산
    new = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            new[m-j-1][n-i-1] = list_2d[i][j]
    return new

 

270도 회전

90도 회전을 세 번 하는 것인데, 즉 -90도 회전하는 것과도 같다. 또는 180 + 90도 회전으로 이해할 수 있다.

def rotate_2d(list_2d):
    n = len(list_2d) # 행 길이 계산
    m = len(list_2d[0]) # 열 길이 계산
    new = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            new[m-j-1][i] = list_2d[i][j]
    return new