[BOJ 16926] 배열 돌리기 1

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

문제

크기가 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의 원소 A_ij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

시간 제한	메모리 제한
1sec	512MB

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ A_ij ≤ 10⁸

---

풀이

$N \times M$ 크기의 배열을 반시계 방향으로 회전시키는 문제다. 배열은 가장 바깥쪽 테두리부터 안쪽까지 여러 개의 층(Layer) 또는 링(Ring)으로 구성되어 있으며, 각 링은 서로 영향을 주지 않고 독립적으로 회전한다.

문제 해결을 위한 핵심 로직은 다음과 같다:

1. 링 분리: 배열에서 회전시켜야 하는 총 링의 개수를 구한다. 이는 배열의 가로, 세로 길이 중 짧은 쪽의 절반인 $\min(N, M) / 2$로 결정된다.

\[\text{Total Layers} = \frac{\min(N, M)}{2}\]

1. 1차원 배열화 (Linearization): 각 링에 속한 원소들을 순서대로 추출하여 1차원 버퍼(buffer)에 저장한다. 추출 순서는 상단 행, 오른쪽 열, 하단 행, 왼쪽 열 순으로 진행하여 하나의 순환 고리를 만든다.

2. 회전 최적화: 회전 횟수 $R$이 각 링의 둘레(원소 개수)보다 클 수 있다. 불필요한 반복 회전을 피하기 위해 실제 회전할 칸 수는 나머지 연산을 활용하여 최적화한다.

\[\text{Effective Rotation} = R \pmod{\text{Buffer Size}}\]

1. 배열 재배치: 최적화된 회전수만큼 버퍼의 시작 인덱스를 이동시켜 다시 원래 배열의 위치에 원소들을 채워 넣는다.

이 방식은 각 원소를 상수 번 방문하므로 전체 시간 복잡도는 $O(N \times M)$이 되며, 제한 시간 1초 내에 충분히 해결 가능하다.

소스코드

Github Link : Source Code

참고 알고리즘 :