[BOJ 16927] 배열 돌리기 2

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

문제

크기가 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 ≤ 10⁹
• min(N, M) mod 2 = 0
• 1 ≤ A_ij ≤ 10⁸

---

풀이

$N \times M$ 크기의 배열을 반시계 방향으로 회전시키는 문제다. 회전 수 $R$이 최대 $10^9$에 달할 정도로 매우 크기 때문에, 단순히 한 칸씩 이동시키는 시뮬레이션을 반복하면 시간 초과가 발생한다. 각 테두리(Ring)가 독립적으로 회전하며, 제자리로 돌아오는 주기가 있다는 점을 이용해 최적화해야 한다.

해결 과정은 다음과 같다:

1. 테두리 분리: 배열의 가장 바깥쪽부터 안쪽으로 들어가며 각각의 독립된 테두리를 구분한다. 테두리의 총 개수는 $\min(N, M) / 2$개다.
2. 주기 계산: 각 테두리를 구성하는 원소의 개수 $L$을 구한다. $L$번 회전하면 테두리는 원래 상태로 돌아오므로, 실제 회전해야 하는 횟수는 $R \pmod L$로 줄일 수 있다.

\[Effective\_R = R \pmod L\]

1. 선형화 및 회전: 각 테두리의 원소들을 순서대로 추출하여 1차원 배열에 저장한다. 이후 $Effective_R$만큼 인덱스를 밀어서 다시 배열의 원래 위치에 배치한다.
2. 결과 출력: 모든 테두리에 대해 위 과정을 반복하여 최종 배열 상태를 얻는다.

배열의 크기가 최대 $300 \times 300$이므로 전체 원소 수는 90,000개다. 각 원소를 상수 번 방문하여 처리하므로 전체 시간 복잡도는 $O(NM)$이며, $R$의 크기에 상관없이 제한 시간 내에 효율적으로 해결이 가능하다.

소스코드

Github Link : Source Code

참고 알고리즘 :