회전 알고리즘

from 2020년 하반기 오후 2번 '회전하는 빙하'

먼저 수식으로 접근해보자.

n x n 정방행렬의 전체 범위 시계 방향 90도 회전

row, col이 0부터 시작한다고 가정하면

for i in range(n):
	for j in range(n):
		temp[j][n - 1 - i] = grid[[i][j]

n x n 정방행렬의 전체 범위 반시계 방향 90도 회전

인덱스 교환만 하면 끝

for i in range(n):
	for j in range(n):
    	temp[n - 1 - j][i] = grid[i][j]

n x m 행렬의 전체 범위 시계 방향 90도 회전

for i in range(n):
	for j in range(m):
    	temp[j][n - 1 - i] = grid[i][j]

n x m 행렬의 전체 범위 반시계 방향 90도 회전

for i in range(n):
	for j in range(m):
    	temp[m - 1 - j][i] = grid[i][j]

행렬 내 일부 회전

ex) [r1, c1] ~ [r2, c2] 범위를 회전한다고 하면

sub = [row[c1:c2+1] for row in grid[r1:r2+1]]

if dir == cw:
	# 시계 방향 90도
	rows, cols = r2 - r1 + 1, c2 - c1 + 1
	for i in range(rows):
		for j in range(cols):
    		sub_rot[j][rows - 1 - i] = sub[i][j]

if dir == ccw:
	# 반시계 방향 90도
	for i in range(rows):
		for j in range(cols):
    		sub_rot[cols - 1 - j][i] = sub[i][j]
        
# 원래 행렬에 덮어쓰기
for i in range(r1, r2 + 1):
	for j in range(c1, c2 + 1):
    	grid[i][j] = sub_rot[i][j]