핵심 아이디어
n×n 크기의 행렬 전체를 반시계 방향으로 90도씩 k번 회전해야 하는 상황을 생각해 봅시다. n×n 행렬은 총 n/2개의 동심원 형태 사각형(레이어)으로 나눌 수 있으며, 중첩 루프를 사용해 각 사각형을 한 번에 하나씩 처리할 수 있습니다.
각 사각형 내부에서는 4개의 요소가 하나의 순환(cycle)을 이루며 이동합니다. 따라서 매 순환마다 해당 4개의 요소를 반시계 방향으로 서로 교환(swap)하면 행렬 전체가 자연스럽게 회전하게 됩니다.
요소 이동 규칙
반시계 방향 회전 시 각 요소는 다음과 같이 이동합니다.
- 위치 (n-1-j, i)의 요소 → 위치 (i, j)로 이동
- 위치 (i, j)의 요소 → 위치 (j, n-1-i)로 이동
- 위치 (j, n-1-i)의 요소 → 위치 (n-1-i, n-1-j)로 이동
- 위치 (n-1-i, n-1-j)의 요소 → 위치 (n-1-j, i)로 이동
이 규칙을 바깥쪽 레이어부터 안쪽 레이어까지 차례대로 적용하고, 이 과정을 k번 반복하면 원하는 만큼의 회전을 얻을 수 있습니다.
C# 구현 예제
using System;
using System.Text;
namespace ConsoleApplication{
public class Matrix{
public void RotateMatrixByKTimes(int[] matrix, int numberOftimes){
int n = matrix.GetLength(0);
for (int k = 0; k < numberOftimes; k++){
for (int i = 0; i < n / 2; i++){
for (int j = i; j < n - i - 1; j++){
int top = matrix[i, j];
// 왼쪽 요소를 위쪽으로 이동
matrix[i, j] = matrix[n - 1 - j, i];
// 아래쪽 요소를 왼쪽으로 이동
matrix[n - 1 - j, i] = matrix[n - i - 1, n - 1 - j];
// 오른쪽 요소를 아래쪽으로 이동
matrix[n - i - 1, n - 1 - j] = matrix[j, n - i - 1];
// 위쪽 요소를 오른쪽으로 이동
matrix[j, n - i - 1] = top;
}
}
}
for (int i = 0; i < n; i++){
StringBuilder s = new StringBuilder();
for (int j = 0; j < n; j++){
s.Append(matrix[i, j] + " ");
}
Console.WriteLine(s);
s = null;
}
}
}
class Program{
static void Main(string[] args){
Matrix m = new Matrix();
int[] matrix = { { 5, 1, 9, 11 }, { 2, 4, 8, 10 }, { 13, 3, 6, 7 }, { 15, 14, 12, 16 } };
m.RotateMatrixByKTimes(matrix, 2);
}
}
}코드 설명
위 코드에서 RotateMatrixByKTimes 메서드는 두 개의 매개변수를 받습니다. 회전할 2차원 배열과 회전 횟수입니다. 외부 루프가 k번 반복되며, 내부의 두 루프는 행렬의 각 레이어를 순회하면서 4개 요소를 임시 변수 top에 저장한 뒤 반시계 방향으로 값을 교환합니다. 모든 회전이 끝나면 StringBuilder를 활용해 최종 행렬을 콘솔에 출력합니다.
예제에서는 4×4 행렬을 2회 회전했는데, 90도를 두 번 회전하는 것은 곧 180도 회전과 같은 결과를 의미합니다.
실행 결과
16 12 14 15 7 6 3 13 10 8 4 2 11 9 1 5
이 알고리즘은 추가 배열 없이 제자리(in-place)에서 회전을 수행하므로 공간 복잡도는 O(1)이며, 시간 복잡도는 행렬의 모든 요소를 k번 순회하므로 O(k × n²)입니다.