[백준] 17276 - 배열 돌리기

https://www.acmicpc.net/problem/17276

 

알고리즘

구현

 

풀이

크기가 n x n인 2차원 정수 배열 X가 있다. (n은 홀수)

X를 45도의 배수만큼 시계방향 혹은 반시계방향으로 돌리려고 한다. X를 시계 방향으로 45° 돌리면 아래와 같은 연산이 동시에 X에 적용되어야 한다. 

-> 시계방향 45도를 기준으로 연산을 짜고 이 연산을 반복해주면 된다. (시계방향 90도: 45도 연산 2번) 반시계방향은 시계방향 + 8번 연산을 시행해주면 된다. 따라서 각도를 360 + 원래 각도로 설정해주었다.

if d < 0:
    # 반시계방향
    # -45: 360+45로 처리하면 동일함
    d += 360

 

연산 

4가지 연산을 시행해주면 된다.

1. 주 대각선 -> 가운데 열 

2. 가운데 열 -> 부 대각선

3. 부 대각선 -> 가운데 행

4. 가운데 행 -> 주 대각선 

5. 나머지는 원래 보드에 있는 값으로 채워줌

 

주 대각선은 (0,0), (1,1), (2,2), (3,3), (4,4)이다. 이 좌표값들의 특징은 i==j 

가운데 열은 (0,2), (1,2), (2,2), (3,2), (4,2)이다. 이 좌표값들의 특징은 i 값에 상관없이 j == 2 (2 = 5//2)

부 대각선은 (0,4), (1,3), (2,2), (3,1), (4,0)이다. 이 좌표값들의 특징은 i+j == N-1

가운데 행은 가운데 열의 반대로, (2,0), (2,1), (2,2), (2,3), (2,4)이다. j 값에 상관없이 i == 2 

 

이 특징을 이용해 새로운 보드를 만들어 회전한 값을 채워준다.

 

먼저 정답을 입력할 보드 ans를 N x N 형태로 만들고, 0으로 값을 채워준다.

ans = [[0] * N for _ in range(N)]

 

# 1. 주 대각선 -> 가운데 열 
if j == mid:
    ans[i][j] = board[i][i]

 

새로운 보드에서 가운데 열에 해당하는 조건은 j == mid인 경우이다.

기존 보드에서 주 대각선의 값을 가운데 열에 넣는 것이다. 기존 보드의 주 대각선 조건은 i == j 이기 때문에 [i, i] 인 경우 == 같은 값인 경우 

 

# 2. 가운데 열 -> 부 대각선
elif i+j == N-1:
    ans[i][j] = board[i][mid]

 

새로운 보드에서 부 대각선에 해당하는 조건은 i+j == N-1

기존의 보드에서 가운데 열에 해당하는 조건은 i 값에 관계없이 j == mid 

 

 

# 3. 부 대각선 -> 가운데 행
elif i == mid:
    ans[i][j] = board[N-j-1][j]

 

새로운 보드에서 가운데 행에 해당하는 조건은 j 값에 관계없이 i == mid, 

기존의 보드에서 부 대각선에 해당하는 조건은 i+j == N-1 이기 때문에 j 값을 기준으로 i 값을 맞춰 (4,0), (3,1) ,... 

# 4. 가운데 행 -> 주 대각선 
elif i == j:
    ans[i][j] = board[mid][j]

 

새로운 보드에서 주 대각선에 해당하는 조건은 i == j,

기존의 보드에서 가운데 행에 해당하는 조건은 j 값에 관계없이 i == mid

 

else:
    ans[i][j] = board[i][j]

 

나머지라 명시한 칸은 new board에서 0인 값 (아직 채워지지 않은 값)

 

이 문제의 키 포인트

테스트케이스가 있다! 즉, 이 시행을 여러번 반복한다.

이 보드를 또 써야하기 때문에 deepcopy를 이용하여 깊은 복사를 수행해야 한다.

깊은 복사란? 참조값의 복사가 아닌 참조된 객체 자체를 복사라는 것 (원본 배열을 보존해야 할 때!!)

 

연산이 끝난 뒤에 깊은 복사를 수행하여 기존의 보드 업데이트

board = deepcopy(ans)

 

전체 코드 

# 배열 돌리기

# 회전을 여러 번 해야하는 경우가 있으므로 deepcopy를 통해 복사 
from copy import deepcopy

T = int(input())
for _ in range(T):
    N, d = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    ans = [[0] * N for _ in range(N)]
    
    if d < 0:
        # 반시계방향
        # -45: 360+45로 처리하면 동일함
        d += 360 
    
    if d == 360 or d == 0:
        for i in board:
            print(*i)
            
    else:        
        for _ in range(d // 45):
            mid = N//2 
            
            for i in range(N):
                for j in range(N):
                    # 1. 주 대각선 -> 가운데 열 
                    if j == mid:
                        ans[i][j] = board[i][i]
                    
                    # 2. 가운데 열 -> 부 대각선
                    elif i+j == N-1:
                        ans[i][j] = board[i][mid]
                        
                    # 3. 부 대각선 -> 가운데 행
                    elif i == mid:
                        ans[i][j] = board[N-j-1][j]
                    
                    # 4. 가운데 행 -> 주 대각선 
                    elif i == j:
                        ans[i][j] = board[mid][j]
                    
                    else:
                        ans[i][j] = board[i][j]
                        
            board = deepcopy(ans)
    
        for k in ans:
            print(*k)