[BOJ/백준] 17470 배열 돌리기 5

import sys
from collections import deque
input = sys.stdin.readline

def calc(i,input_list,flag):
    if i == 1:
        input_list.rotate(2)
    elif i == 2:
        input_list.reverse()
        input_list.rotate(2)
    elif i == 3:
        a,b = input_list.popleft(),input_list.popleft()
        input_list.insert(1,a)
        input_list.insert(3,b)
    elif i == 4:
        a = input_list.popleft()
        input_list.rotate(1)
        b = input_list.pop()
        input_list.rotate(1)
        input_list.append(a)
        input_list.append(b)
    elif flag and i ==6:
        a = input_list.popleft()
        input_list.rotate(1)
        b = input_list.pop()
        input_list.rotate(1)
        input_list.append(a)
        input_list.append(b)
    elif flag and i == 5:
        a,b = input_list.popleft(),input_list.popleft()
        input_list.insert(1,a)
        input_list.insert(3,b)
        



N,M,R = map(int,input().split())
half_N = N//2
half_M = M//2
arr = [list(map(int,input().split())) for _ in range(N)]

arr_divide = {}
for i in range(4):
    temp = []
    quo = i//2
    mod = i%2
    start_x = quo*(N//2)
    end_x = (quo+1)*(N//2)
    start_y = mod*(M//2)
    end_y = (mod+1)*(M//2)
    for x in range(start_x,end_x):
        tmp = []
        for y in range(start_y,end_y):
            tmp.append(arr[x][y])
        temp.append(tmp)
    arr_divide[i+1] = temp
command_cnt = [0 for _ in range(7)]

command_list = list(map(int,input().split()))

small_list = deque([1,2,3,4])


mini_rotate = deque([0,1,2,3])

for i in command_list:
    calc(i,small_list,True)
    calc(i,mini_rotate,False)
position = [[0,0],[0,M//2-1],[N//2-1,0],[N//2-1,M//2-1]]
one,two,three = mini_rotate.popleft(),mini_rotate.popleft(),mini_rotate.popleft()
for i in range(4):
    origin = position[one]
    left_origin = position[two]
    bottom_origin = position[three]
    if origin[0] == left_origin[0] and origin[1] == bottom_origin[1] :
        if origin[1] > left_origin[1]:
            dy = -1
        else:
            dy = 1
        if origin[0] > bottom_origin[0]:
            dx = -1
        else:
            dx = 1
        temp = []
        for x in range(abs(bottom_origin[0]-origin[0])+1):
            tmp = []
            for y in range(abs(origin[1] - left_origin[1])+1):
                tmp.append(arr_divide[i+1][origin[0]+x*dx][origin[1]+y*dy])
            temp.append(tmp)
        arr_divide[i+1] = temp
    else:
        if origin[0] > left_origin[0]:
            dy = -1
        else:
            dy = 1
        
        if origin[1] > bottom_origin[1]:
            dx = -1
        else:
            dx = 1
        temp = []

        for x in range(abs(bottom_origin[1]-origin[1])+1):
            tmp = []
            for y in range(abs(left_origin[0]-origin[0])+1):
                tmp.append(arr_divide[i+1][origin[0]+dy*y][origin[1]+dx*x])

            temp.append(tmp)
        arr_divide[i+1] = temp

last_N= len(arr_divide[1])*2
last_M = len(arr_divide[1][0])*2

result = [[0 for _ in range(last_M)] for _ in range(last_N)]
for i in range(4):
    idx = small_list.popleft()
    quo = i//2
    mod = i%2
    start_x = quo*(last_N//2)
    start_y = mod*(last_M//2)
    my_array = arr_divide[idx]
    for x in range(last_N//2):
        for y in range(last_M//2):
            result[start_x+x][start_y+y] = my_array[x][y]


for x in range(last_N):
    for y in range(last_M):
        print(result[x][y],end=' ')
    print()

    

 

 

배열 돌리기 시리즈의 5번째이다.

 

이 배열돌리기는 전체를 돌리면 무조건 시간초과가 날수밖에 없다.

 

왜냐하면 최대 100*100의 행렬이 오는데 그걸 200만번 수행을 하면 터질수 밖에 없다.

 

그렇다 면 이 문제를 해결하는 방법은 다음과 같다.

 

이 문제에서 행렬을 크게 4부위로 나눌수 있다.

 

처음 배열을 다음과 같이 4등분을 해주자(문제에서는 1 2/ 3 4 가 아니라, 1 2 / 4 3 형태이지만, 그냥 편하대로 하면 된다.)

 

 

그러면 1번 돌리기는 다음과 같이 표현할 수 있다.

위 아래의 배열이 바뀌고, 그리고 그안의 있는 값도 상하반전이 된 것을 알 수 있다.

 

 

2번 돌리기는

 

좌우 반전이 되고, 그리기 도구에서 안의 숫자를 좌우반전을 하는게 없어서 표현 못했지만, 그 안에 있는 작은 배열들도 좌우 반전이 되어야한다.

 

 

3번 돌리기는

 

오른쪽으로 90도 돌면서 그 안의 있는 값들도 90도로 돌리면 된다.

 

4번 돌리기는 왼쪽으로 90도로 돌리고, 그 안의 배열들도 같이 왼쪽으로 90도를 돌리면 된다.

 

 

5번 돌리기는 3번돌리기와 똑같이 전체 배열의 이동은 같지만, 안의 배열이 돌아가지 않는 모습이다.

 

 

그리고 6번 돌리기는 4번돌리기와 전체배열의 이동은 같지만 안의 배열이 돌아가지 않는 모습이다.

 

 

이렇게 4등분을 해보면 우리는 알 수 있는 사실이 있다.

 

전체 배열을 전부 돌릴필요가 없다는 것이다.

 

1~6번 돌리기를 간략하게 표현할 수 있는 2*2 배열을 돌리기만 하면 된 다는 것을 알 수 있다.

 

그러면 그 안에 있는 배열들이 돌아가는 것은 어떻게 표현하느냐이다.

 

 위와 같이 한 배열이 있다고 하면, 우리는 네 꼭지점의 위치를 알면 전체 배열이 어떻게 모양이 변한지 알 수 있다.

 

이러한 특성을 이용해서 

 

mini_rotate에는 각 꼭지점의 위치를 표현한 (0,1,2,3)을 상황에 맞게 돌려주면서, 작은 배열에서 1~4번 돌리기에 해당될때 어떻게 회전되는지를 표현해주었다.

 

그리고 small_list는 전체 배열을 4등분을 해서, 각 등분된 배열을 1,2,3,4로 매칭시키고, 1~6번 돌리기에 맞게 회전을 시켜 주었다.

 

mini_rotate를 돌릴때 주의 해야할 것은 나는 행을 x  열을 y로 표현하는 편이다. 돌리다 보면

 

행과 열이 뒤바뀌어서 행이 dy 열로 이동하는 것이 dx로 뒤바뀔때가 있을 것이다.

 

그러면 이걸 어떻게 구분할 것이냐,

 

위의 변수명을 잘못 선언했지만 다음과 같다.

 

원본 배열에서 (0,0) 이 부분을 origin이라 하겠다.

 

그리고 (0,M//2) 이부분을 right_origin(코드에서는 left_origin) 이라 부르겠다.

 

그리고 (N//2,0) 이 부분을 bottom_origin이라 부르겠다.

 

 

그러면 우리가 전부 회전을 하고 난뒤에 바뀐 위치에 있는 origin, right_origin, bottom_origin이 있을것이다.

 

그러면 행과 열이 뒤바뀌었는지 아는 방법은 다음과 같다.

 

 

origin의 x좌표와 right_origin의 x좌표가 같고, orign과 bottom_origin의 y좌표가 동일하다면,

 

우리는 평소에 알던 x,y의 형태로 가면 될것이다.

 

이 dx,dy가 +인지 -인지는 대소로 구분하면 된다.

 

이렇지 않을 경우엔 행과 열이 바뀐 90도나 270도로 회전한 모습일것이므로, dy와 dx를 변경해서 구해주면 된다.

 

 

이렇게 배열들을 전부 회전 시킨다음

 

mini_rotate의 순서에 맞게, 전체 배열에 넣어주면 문제를 해결 할 수 있다.

 

이 문제는 원본배열을 4등분을 해서 축약해서 돌릴수 있느냐, 그리고 그 안의 작은 배열도 네꼭지점으로 나누어서 돌릴 수 있느냐를 물어본 문제 같다.

 

또한 이렇게 회전을 했을때, dx,dy와 배열을 복사할때의 위치를 어떻게 찾을지 구현을 하는데 어려운점이 많았다.

 

이 문제에서 시간이 가장 오래 걸렸던 것은, dx,dy의 방향이 바뀔때를 찾는 것이었다.

 

그리고 위의 6가지 유형에 맞게, deque를 rotate,pop,insert,popleft를 해야할지 고민했던게 오래걸렸다.

 

단순해 보이지만, 여러가지 고민을 하게 만들어주었던 문제였다.