[BOJ/백준] 16927 배열 돌리기 2 파이썬

문제 링크 : https://www.acmicpc.net/problem/16927

16927번: 배열 돌리기 2

 

2차원 배열을 규칙에 바깥부터 한꺼풀씩 돌리는 것이다.  반시계 방향으로 돌리는 것이다.

 

그냥 쉽게 숫자 하나씩 반시계방향으로 한칸씩 밀면서 하려고 보니 최대 10^9 만큼 돌려야한다.

그러므로 한바퀴 돌릴때 원소의 개수를 구해서 모듈러 연산을 이용하여 횟수를 줄이자.

 

4x4 행렬일 경우 첫번째 꺼풀의 원소 개수는 (4-1)*2+(4-1)*2=12개이다. 그러므로 12바퀴 돌리면 제자리로 오게된다.

이를 이용하여 연산횟수를 줄이자. 이제 이 횟수만큼 반시계 방향으로 돌리면 된다.

줄여도 횟수가 많다. 더 줄여보자.

회전하려는 꺼풀을 1자로 펼치고 인덱스를 더하는 방식으로 한다면 더 빠르게 돌릴 수 있다.

 

예를 들어

1 2 3

8 9 4

7 6 5

라고 한다면

 

첫번째 꺼풀은 1 2 3 4 5 6 7 8이다

여기서 12바퀴 회전한다면 각 원소의 위치는 (idx-12)%8이 될 것이다.

이때 idx-12가 음수가 되는데 이는 8+(음수결과값)으로 계산이된다. 이는 모듈러 연산 성질이다.

 

가장 중요한 것이 한꺼풀씩 빼내는 것이다.

회전의 시작 인덱스는 (0,0),(1,1),(2,2) 이런식으로 최대 min(n,m)만큼 돌리게 된다.

또한 한꺼풀씩 들어갈때 n과 m은 2씩 줄어든다.

이것 직접 그려보면 금방 이해된다.

나는 반복문 4개로 테두리별로 빼서 임시 배열에 저장하고, 다시 테두리 돌면서 값을 업데이트 시켰다.

이는 코드를 보면 금방 이해가 갈 것이다.

 

from sys import stdin

input = stdin.readline

n,m,r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

def solv():
    global n,m
    p = 0
    for _ in range(min(n,m)//2):
        rotate(p,p)
        p += 1
        n -= 2
        m -= 2

    for row in board:
        print(*row)
def rotate(sx,sy):
    global board
    length = (n-1)*2+(m-1)*2
    row = [0]*length
    idx = 0
    for y in range(sy, sy+m-1):
        row[(idx-r)%length] = board[sx][y]
        idx+=1
    for x in range(sx, sx+n-1):
        row[(idx-r)%length] = board[x][sy+m-1]
        idx += 1
    for y in range(sy+m-1, sy,-1):
        row[(idx-r)%length] = board[sx+n-1][y]
        idx += 1
    for x in range(sx+n-1, sx,-1):
        row[(idx-r)%length] = board[x][sy]
        idx+=1

    idx = 0
    for y in range(sy, sy+m-1):
        board[sx][y] = row[idx]
        idx += 1
    for x in range(sx, sx+n-1):
        board[x][sy+m-1] = row[idx]
        idx += 1
    for y in range(sy+m-1, sy,-1):
        board[sx+n-1][y] = row[idx]
        idx += 1
    for x in range(sx+n-1, sx,-1):
        board[x][sy] = row[idx]
        idx += 1
solv()