[BOJ 16927] 배열 돌리기 2

BOJ 16926 배열 돌리기 1에서 회전수 R이 최대 $10^9$로 커진 버전이다.

1. 가장 바깥 껍데기를 원형큐로 만든다. 이때의 큐의 크기를 Q라 하자.
2. 회전수는 R이 아니라 $Q \mod R$이므로 효율적으로 돌린다.
3. 다시 큐의 앞부분부터 껍데기를 채운다.
4. 안쪽 껍데기가 더 이상 없을 때 까지 반복한다.

따라서 껍데기를 돌리는 함수를 정의했다.
rotate_part(A, x1, y1, x2, y2, R):
A: NxM 행렬
(x1, y1): 행렬의 좌상단
(x2, y2): 행렬의 우하단
R: 회전 수

또, 안쪽 껍데기로 들어가려면 행렬의 좌상단의 좌표값은 1씩 증가하고 우하단의 좌표값은 1씩 감소하는것을 이용하면 된다.

import sys
#sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

from collections import deque

def print_matrix(A, N, M):
    for i in range(N):
        for j in range(M):
            print(A[i][j], end=' ')
        print()
    print()

def rotate_part(A, x1, y1, x2, y2, R):
    q = deque()
    for j in range(y1, y2):
        q.append(A[x1][j])
    for i in range(x1, x2):
        q.append(A[i][y2])
    for j in range(y2, y1, -1):
        q.append(A[x2][j])
    for i in range(x2, x1, -1):
        q.append(A[i][y1])
    
    Q = len(q)
    for _ in range(R % Q):
        element = q.popleft()
        q.append(element)
    
    for j in range(y1, y2):
        A[x1][j] = q.popleft()
    for i in range(x1, x2):
        A[i][y2] = q.popleft()
    for j in range(y2, y1, -1):
        A[x2][j] = q.popleft()
    for i in range(x2, x1, -1):
        A[i][y1] = q.popleft()


N, M, R = map(int, input().split())
A = []
for _ in range(N):
    A.append(list(map(int, input().split())))

for i in range(min(N, M) // 2):
    rotate_part(A, i, i, N - 1 - i, M - 1 - i, R)

print_matrix(A, N, M)