[Algoritm] 행렬 회전 (Python 구현)

프로그래머스에서 제공하는 카카오 2020년 신입 개발자 블라인드 코딩 테스트 1차 문제 3번을 풀어 보았다.

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

 

해당 문제는 어떤 알고리즘을 사용할 것인가를 알아내는 것보다 구현력이 필요한 문제였다고 생각한다.

 

해당 문제의 경우 제한 사항의 크기가 작기 때문에 모든 경우를 확인하는 완전 탐색으로 풀이가 가능한데, 행렬의 회전과 범위를 설정하는 것이 중요했다.

 

문제를 해결하기 위해서는 2차원 행렬의 회전을 구현해야 했다.

회전구현은 간단 하지만, 익숙하지 않다면, 바로 생각나지 않을 수 있다고 생각한다. 한 번쯤 정리해 놓으면 도움이 될 듯하다.

🗝 2차원 행렬 회전

해당 문제에서는 행과 열이 동일한 정사각형이 문제로 주어졌지만, 일반적인 상황을 고려해서 행과 열이 다른 n x m 행렬을 시계 방향으로 회전시켜 보았다.

 

위의 그림처럼 3 x 4 행렬은 회전 후 4 x 3 행렬이 되어야 한다. (n x m -> m x n)

기존 행렬의 열(column)의 이동은 변화될 행렬의 행(row)의 이동으로

기존 행렬의 행(row)의 이동은 변화될 행렬의 열(column)의 역 이동으로 움직인다는 것을 알 수 있다.

def rotate(arr):
    n = len(arr)		# 기존 행렬의 행의 길이
    m = len(arr[0])		# 기존 행렬의 열의 길이
    
    new_arr = [[0] * n for _ in range(m)]	# 새로운 행렬 생성(0으로 초기화), 기존 행렬과 행, 열이 뒤바뀜

    for i in range(n):		# 기존 행렬의 행 이동
        for j in range(m):	# 기존 행렬의 열 이동
            new_arr[j][n - 1 - i] = arr[i][j]
    return new_arr

위 그림을 코드로 표현하면 위와 같다.

 

새로운 행렬(new_arr)의 행은 기존 행렬의 열(j)과 같다.

새로운 행렬의 열은 기존 행렬의 행(i)의 역과 같다. 다르게 표현하면 기존 행렬의 행(row)의 위치를 새로운 행렬의 열(column) 가장 뒤에서부터 대입해주면 된다. (n -1 - i)

 

새로운 행렬의 열(column)의 길이는 기존 행렬의 행(row)의 길이와 같고 배열에서 index 접근을 위해서 n - 1부터 접근한다.

 

반시계 회전

def rotate(arr):
    n = len(arr)		# 기존 행렬의 행의 길이
    m = len(arr[0])		# 기존 행렬의 열의 길이
    
    new_arr = [[0] * n for _ in range(m)]	# 새로운 행렬 생성(0으로 초기화), 기존 행렬과 행, 열이 뒤바뀜

    for i in range(n):		# 기존 행렬의 행 이동
        for j in range(m):	# 기존 행렬의 열 이동
            new_arr[m - 1 - j][i] = arr[i][j]
    return new_arr

반시계 방향의 회전은 동일한 방법으로 위와 같이 표현할 수 있다.