[백준 16926번] 파이썬 - 배열 돌리기1

백준 16926 - 배열 돌리기1

시간 제한 1초, 메모리 제한 512MB

# 조건

• 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다.
• 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

• 예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

• 배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

• 첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.
• 둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

• 입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 10^8

# 접근 방법

• 주어진 회전의 수를 모두 실행시킨다면 최악의 경우 O(300 * 300 * 1000)이 되어 시간 초과가 발생한다.
• 따라서, 회전의 규칙을 찾아 주기 위해서 각 자리의 수가 제자리로 돌아오는 것을 살펴보자.
  • 예제의 4 X 4의 배열의 경우 (0, 0)의 1이 다시 제자리로 돌아오기 위해서는 12번의 회전이 필요하고
  • (1, 1)의 6이 제자리로 돌아오기 위해서는 4번의 회전이 필요하다.
    • 즉, 가장 바깥 테두리는 3번의 행 + 3번의 열 + 3번의 행 + 3번의 열 이동을 거친 후에 제자리로 돌아오고
    • 바로 안쪽의 회전은 1번의 행 + 1번의 열 + 1번의 행 + 1번의 열 이동을 거친다.
  • 여기서 찾을 수 있는 규칙은 가장 바깥의 경우
    • 주어진 N, M에서 (N-1) * 2 + (M-1) * 2의 연산이 필요하고
    • 그 다음은 (N-3) * 2 + (M-3) * 2의 연산 => 바깥 쪽에서 행, 열이 2개씩 줄어든 연산 횟수이다.
    • 여기서 빼는 수는 (1 + cnt * 2)를 통하여 기록해주고 N,M 중 하나는 짝수를 보장하므로 0이하가 된다면 종료해주면 된다.
  • 즉, 회전해야되는 횟수를 시작 위치에서 제자리로 돌아오는 카운트만큼 나눠준 나머지만큼만 회전을 하면 된다.
• 이후 회전을 시키는 것은 deque의 rotate를 이욯애준다.
  • 현재 회전시키는 사각형의 원소와 좌표들을 val_q와 loc_q에 담아준 후 회전해야되는 횟수만큼 q1.rotate 해주고
  • q2의 첫번째 원소부터 q1에 있는 값을 채워넣어주면 된다.
  • 이 때, 가장 마지막 원소에서 출발점으로 돌아오므로 val_q와 loc_q를 pop 한번 해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

N, M, R = map(int, input().split())  
rotate = [R] * (N//2)  
arr = [[*map(int, input().split())] for _ in range(N)]  
cnt = 0  
# 제자리로 돌아오는 카운트  
# 1 depth 안쪽으로 갈수록 행, 열이 2개씩 좁아지므로 카운트 수는 4씩 줄어든다.  
# (N-(1 + cnt * 2)) * 2 + (M-(1 + cnt * 2)) * 2  
while N - (2*cnt + 1) > 0 and M - (2*cnt + 1) > 0:  
    rotate[cnt] = R % ((N - (2*cnt + 1))*2 + (M - (2*cnt + 1))*2)  
    cnt += 1  

# 반시계방향  
di, dj = [1, 0, -1, 0], [0, 1, 0, -1]  
# 제일 안쪽에 있는 정사각형의 시작 좌표는 min(N, M) // 2 이다.  
for depth in range(min(N, M) // 2):  
    si, sj = depth, depth  
    val_q = deque([arr[si][sj]])  
    loc_q = deque([(si, sj)])  
    # 가장 바깥의 정사각형부터 반시계 방향으로 회전시켜야 되는 원소와 좌표들 넣어주기  
    for d in range(4):  
        while True:  
            ni, nj = si + di[d], sj + dj[d]  
            if depth <= ni < N-depth and depth <= nj < M-depth:  
                val_q.append(arr[ni][nj])  
                loc_q.append((ni, nj))  
                si, sj = ni, nj  
            else:  
                break  
    # 시작 위치가 한번 더 들어오므로 pop 해주기  
    val_q.pop()  
    loc_q.pop()  
    # 회전시켜야 되는 값만큼 회전시켜주기  
    val_q.rotate(rotate[depth])  
    # 회전 시킨 값 넣어주기  
    while loc_q:  
        i, j = loc_q.popleft()  
        v = val_q.popleft()  
        arr[i][j] = v  

for i in arr:  
    print(*i)