[백준 16927번] 파이썬 - 배열 돌리기2

백준 16927 - 배열 돌리기2

시간 제한 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 ≤ 10^9
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 10^8

# 접근 방법

• 브루트 포스로 R만큼 회전시키면 당연히 시간 초과가 발생하는 문제이다.
• 따라서, 회전 규칙을 찾아주어야 되는데 제일 바깥 테두리가 회전할 때, [0][0] 자리의 수가 제자리로 돌아오기 위해서는 아래로 N-1, 오른쪽으로 M-1, 위로 N-1, 왼쪽으로 M-2번 즉, 2N - 2 + 2M - 2번의 이동이 필요하다.
  • 한 칸 내부로 들어갈 때 마다, 2개의 행과 2개의 열이 줄어 들기 때문에, r과 c의 값이 0보다 클 때 까지 각 테두리에서 원점으로 돌아오기 위해 필요한 횟수를 R을 나눈 나머지의 값으로 기록해준다.
• 이제 배열의 회전을 해주면 되는데, DEQUE의 rotate를 활용해준다.
• 현재 돌릴 테두리의 왼쪽 상단 모서리를 기준으로 시계 방향으로 돌며 q에 넣어준다.
  • 이 때 주의할 점은, 시작점을 제외한 모서리를 2번 넣지 않도록 조심해준다.
• rotation에 기록된 값을 음수로 넣어 rotate 해준 후 마찬가지고 원본 배열에 돌아가면서 기록해주면 된다.

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

N, M, R = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
rotation = []
r, c = N, M

while r > 0 and c > 0:
    rotation.append(R % (r*2 + c*2 - 4))
    r-=2
    c-=2

si, sj, ei, ej = 0, 0, N-1, M-1
cnt = 0
while si <= ei and sj <= ej and cnt < len(rotation):
    q = deque()
    for j in range(sj, ej+1):
        q.append(arr[si][j])

    for i in range(si+1, ei+1):
        q.append(arr[i][ej])

    for j in range(ej-1, sj-1, -1):
        q.append(arr[ei][j])

    for i in range(ei-1, si, -1):
        q.append(arr[i][sj])

    q.rotate(-rotation[cnt])

    for j in range(sj, ej+1):
        arr[si][j] = q.popleft()

    for i in range(si+1, ei+1):
        arr[i][ej] = q.popleft()

    for j in range(ej-1, sj-1, -1):
        arr[ei][j] = q.popleft()

    for i in range(ei-1, si, -1):
        arr[i][sj] = q.popleft()
    si += 1
    sj += 1
    ei -= 1
    ej -= 1
    cnt += 1

for i in range(N):
    print(*arr[i])