[알고리즘] 백준 | 배열 돌리기 Python (16926, 16927)

알고리즘 문제를 풀다보면 2중배열을 조작하여 풀어야 하는 유형이 종종 보인다.

자주 나오는 유형은 그 풀이공식을 어느정도 외워두는것이 좋은 듯 하다.

---

문제

크기가 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 (16926번) / 1 ≤ R ≤ 10**9 (16927번)
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

---

 먼저 "반시계 방향" 으로 회전을 어떻게 할 것인가? 를 두고 한참 고민했다. 모두가 같은 방향으로 회전하는 것이 아니라 총 4가지 방향으로 회전해야 하기 때문에

1. 어느 포인트에서 회전방향을 바꾸어야 하는지
2. 얼마만큼 길이를 해당 방향으로 회전해야 하는지

를 구하는게 관건이었다.

 

이 문제를 풀기 위해서는 "이중배열을 1차원 배열로 풀기" 가 포인트이다.

1. 이중배열을 1차원 배열로 풀기

1차원 배열로 풀기 위해서는 회전하는 기준이 되는 묶음 (이하 루프) 의 갯수를 파악해야 한다. 제한조건에서 n과 m중 최솟값은 2의 배수임을 명시했기 때문에 루프가 생기지 않는 가운데 부분은 고려하지 않는다.

 

가로, 세로의 최솟값을 2로 나눈 몫 만큼 루프가 형성된다.

# 1. 가로 4, 세로 5
standard = min(4, 5) // 2 # => 2

# 2. 가로 5, 세로 4
standard = min(5, 4) // 2 # => 2

# 3. 가로 2, 세로 4
standard = min(2, 4) // 2 # => 1

# 4. 가로 6, 세로 2
standard = min(6, 2) // 2 # => 1

 

따라서 새로 만들어질 1차원 배열도 루프의 갯수만큼 생성될 것이다.

 

위, 오른쪽, 아래, 왼쪽 순서대로 배열을 새로 정의하는데 이때 "모서리에 있는 숫자" 의 중복 처리를 주의해야 한다.

위와 아래에는 모든 모서리를 포함하도록 하고, 오른쪽과 왼쪽은 모서리를 제외한 변의 숫자만을 처리하도록 한다.

n, m, r = map(int, input().split()) # n = 세로 / m = 가로 / r = 회전 수
board = [list(map(int, input().split())) for _ in range(n)]
new_board = [[0]*m for _ in range(n)]
q = deque()
# 2차원 배열을 1차원 배열로 펼치기
loop_count = min(n, m) // 2

for i in range(loop_count):
    q.clear()
    # 위쪽
    q.extend(board[i][i:m-i])
    # 오른쪽 (모서리 제외)
    q.extend([row[m-i-1] for row in board[i+1:n-i-1]])
    # 아래쪽
    q.extend(board[n-i-1][i:m-i][::-1])
    # 왼쪽 (모서리 제외)
    q.extend([row[i] for row in board[i+1:n-i-1][::-1]])
    q.rotate(-r)

 

또한 위와 아래는 숫자 처리 방향이 반대이고, 오른쪽과 왼쪽도 서로 반대방향이므로 아래쪽과 왼쪽의 수를 배열로 생성할때에는 [::-1] 을 하여 순서를 반대로 되게 해준다.

 

2. r만큼 회전시키기

루프를 1차원 배열로 만든 뒤 r의 횟수만큼 회전을 시켜줌에 따라 pop, popleft, append, appendleft 가 발생한다.

문제는 "반시계 방향" 이므로 popleft와 append가 일어나게 된다.

 

하지만 python의 deque 에서는 회전을 동작하는 rotate 함수가 있으므로 이를 사용해 준다.

왼쪽으로 회전할때는 음의값을, 오른쪽으로 회전할때는 양의 값을 인자로 받는다.

from collections import deque

dq = deque()
dq.extend([1, 2, 3, 4])

# 좌로 회전
dq.rotate(-2) # => [3, 4, 1, 2]

# 우로 회전
dq.rotate(2) # => [3, 4, 1, 2]

# r 만큼 좌로 회전 (반시계 방향)
q.rotate(-r)

 

3. 1차원 배열을 2차원 형태로 가공하기

회전이 완료된 1차원 배열을 다시 원래 자리의 2차원 배열 형태로 만들어 주어야 한다.

별다른 공식은 없고 위치를 주의하여 넣어주면 된다.

    # 위
    for j in range(i, m-i):
        new_board[i][j] = q.popleft()

    # 오른쪽
    for j in range(i+1, n-i-1):
        new_board[j][m-i-1] = q.popleft()
    # 아래쪽
    for j in range(m-i-1, i-1, -1):
        new_board[n-i-1][j] = q.popleft()

    for j in range(n-i-2, i, -1):  # 왼쪽
        new_board[j][i] = q.popleft()

q 에는 회전이 완료된 수들이 순서대로 들어있다. 1차원 배열에 담았던 순서대로 위 -> 오른쪽 -> 아래쪽 -> 왼쪽 으로 처리해 준다.

이때 for-loop 에서 range(a, b, c) 형태는 a 부터 b 까지 c의 값만큼 더하여 처리한다는 뜻이다.

 

---

전체 풀이

import sys
from collections import deque
sys.stdin = open("input.txt", "r")
n, m, r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
new_board = [[0]*m for _ in range(n)]
q = deque()
# 2차원 배열을 1차원 배열로 펼치기
loop_count = min(n, m) // 2

for i in range(loop_count):
    q.clear()
    # 위쪽
    q.extend(board[i][i:m-i])
    # 오른쪽 (모서리 제외)
    q.extend([row[m-i-1] for row in board[i+1:n-i-1]])
    # 아래쪽
    q.extend(board[n-i-1][i:m-i][::-1])
    # 왼쪽 (모서리 제외)
    q.extend([row[i] for row in board[i+1:n-i-1][::-1]])
    q.rotate(-r)

    # 다시 board 정렬하기
    # 위
    for j in range(i, m-i):
        new_board[i][j] = q.popleft()

    # 오른쪽
    for j in range(i+1, n-i-1):
        new_board[j][m-i-1] = q.popleft()
    # 아래쪽
    for j in range(m-i-1, i-1, -1):
        new_board[n-i-1][j] = q.popleft()

    for j in range(n-i-2, i, -1):  # 왼쪽
        new_board[j][i] = q.popleft()

for row in new_board:
    print(*row)

"""
[입력]
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
"""

"""
[출력]
3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14
"""

 

16926번과 16927번의 문제가 동일하여 같은 풀이로 제출하면 되는데

앞의것은 실버레벨이고 뒤의것은 골드레벨인것을 보아, 16926번을 풀때 deque를 활용하지 않고 순수 배열 처리로만 했을때 풀리더라도 같은 풀이로 16927번을 풀었을때 타임아웃이 나지 않을까 싶다.

제한 조건을 보면 16926은 R의 값이 최대 1000 이지만 16927은 최대 10**9 값을 가질수 있다.

 

위 풀이로는 두 문제 전부 python3으로 체점하여 통과 가능하다.