2차원 배열로 구성된 행렬이 주어졌을 때, 이를 시계 방향으로 90도 회전해야 합니다. 회전 결과는 마지막 행이 첫 번째 열이 되고, 두 번째 행은 두 번째 열, 첫 번째 행은 세 번째 열이 됩니다. 여기서 핵심 과제는 추가 공간(임시 배열)을 사용하지 않고 제자리(in-place)에서 회전을 수행하는 것입니다.
입력 및 출력 예시
예시 1
입력:
int arr[row_col_size][row_col_size] = { { 5, 1, 4},
{ 9, 16, 12 },
{ 2, 8, 9}}출력:
2 9 5 8 16 1 9 12 4
설명: 정수형 2차원 배열이 입력으로 주어지며, 이를 시계 방향으로 90도 회전합니다.
회전 전:
{ { 5, 1, 4},
{ 9, 16, 12 },
{ 2, 8, 9}}
회전 후:
2 9 5
8 16 1
9 12 4예시 2
입력:
int arr[row_col_size][row_col_size] = { { 2, 1, 9},
{ 11, 6, 32 },
{ 3, 7, 5}}출력:
3 11 2 7 6 1 5 32 9
설명: 마찬가지로 정수형 2차원 배열을 받아 시계 방향으로 90도 회전한 결과입니다.
접근 방법
1. 기본 접근법(Naive Approach) - 레이어별 순환 교환
row_col_size 크기의 정수형 2차원 배열(행렬)을 입력받습니다.
배열 데이터를 Rotate_ClockWise(arr) 함수에 전달합니다.
Rotate_ClockWise(arr) 함수 내부 동작:
i를 0부터 row_col_size / 2보다 작을 때까지 반복합니다.
내부 루프에서 j를 i부터 row_col_size - i - 1보다 작을 때까지 반복합니다.
각 반복에서 네 개의 모서리 요소를 임시 변수 ptr을 활용해 순환적으로 교환합니다. 즉, arr[i][j] → arr[row_col_size - 1 - j][i] → arr[row_col_size - 1 - i][row_col_size - 1 - j] → arr[j][row_col_size - 1 - i] 순서로 값을 돌려가며 저장합니다.
마지막으로 이중 루프를 사용해 회전된 행렬 전체를 출력합니다.
이 방법은 행렬의 가장 바깥쪽 레이어부터 안쪽 레이어까지 한 번에 네 개의 요소씩 회전시키는 방식입니다.
2. 효율적인 접근법(Efficient Approach) - 전치 후 행 뒤집기
row_col_size 크기의 정수형 2차원 배열(행렬)을 입력받습니다.
배열 데이터를 Rotate_ClockWise(arr) 함수에 전달합니다.
Rotate_ClockWise(arr) 함수 내부 동작:
전치(Transpose): i를 0부터 row_col_size까지 반복하고, 내부 루프에서 j를 0부터 row_col_size - i까지 반복하면서 arr[i][j]와 arr[row_col_size - 1 - j][row_col_size - 1 - i]의 값을 서로 교환하여 대각선 기준으로 요소를 뒤집습니다.
행 뒤집기(Reverse Rows): i를 0부터 row_col_size / 2까지 반복하고, 내부 루프에서 j를 0부터 row_col_size까지 반복하면서 arr[i][j]와 arr[row_col_size - 1 - i][j]의 값을 서로 교환하여 위아래 행을 뒤집습니다.
마지막으로 이중 루프를 사용해 회전된 행렬 전체를 출력합니다.
이 방법은 먼저 행렬을 전치한 뒤 각 행의 순서를 뒤집으면 시계 방향 90도 회전과 동일한 결과가 나온다는 수학적 원리를 활용합니다.
기본 접근법 코드 예제
#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3
void Rotate_ClockWise(int arr[row_col_size][row_col_size]){
for(int i = 0; i < row_col_size / 2; i++){
for(int j = i; j < row_col_size - i - 1; j++){
int ptr = arr[i][j];
arr[i][j] = arr[row_col_size - 1 - j][i];
arr[row_col_size - 1 - j][i] = arr[row_col_size - 1 - i][row_col_size - 1 - j];
arr[row_col_size - 1 - i][row_col_size - 1 - j] = arr[j][row_col_size - 1 - i];
arr[j][row_col_size - 1 - i] = ptr;
}
}
}
int main(){
int arr[row_col_size][row_col_size] = { { 5, 1, 4},{ 9, 16, 12 },{ 2, 8, 9}};
Rotate_ClockWise(arr);
cout<<"추가 공간 없이 행렬을 시계 방향으로 90도 회전한 결과: \n";
for(int i = 0; i < row_col_size; i++){
for(int j = 0; j < row_col_size; j++){
cout << arr[i][j] << " ";
}
cout << '\n';
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
2 9 5 8 16 1 9 12 4
효율적인 접근법 코드 예제
#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3
void Rotate_ClockWise(int arr[row_col_size][row_col_size]){
// 1단계: 행렬 전치(Transpose)
for(int i = 0; i < row_col_size; i++){
for(int j = 0; j < row_col_size - i; j++){
int ptr = arr[i][j];
arr[i][j] = arr[row_col_size - 1 - j][row_col_size - 1 - i];
arr[row_col_size - 1 - j][row_col_size - 1 - i] = ptr;
}
}
// 2단계: 행 순서 뒤집기(Reverse Rows)
for(int i = 0; i < row_col_size / 2; i++){
for(int j = 0; j < row_col_size; j++){
int ptr = arr[i][j];
arr[i][j] = arr[row_col_size - 1 - i][j];
arr[row_col_size - 1 - i][j] = ptr;
}
}
}
int main(){
int arr[row_col_size][row_col_size] = { { 5, 1, 4},{ 9, 16, 12 },{ 2, 8, 9}};
Rotate_ClockWise(arr);
cout<<"추가 공간 없이 행렬을 시계 방향으로 90도 회전한 결과: \n";
for(int i = 0; i < row_col_size; i++){
for(int j = 0; j < row_col_size; j++){
cout << arr[i][j] << " ";
}
cout << '\n';
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
2 9 5 8 16 1 9 12 4
정리
두 방법 모두 O(1)의 추가 공간만 사용하므로 공간 복잡도 측면에서는 동일하지만, 전치 후 행을 뒤집는 효율적인 접근법이 로직이 더 단순하고 직관적이라 실무에서 선호되는 편입니다. 두 방법 모두 N×N 정방 행렬에 적용할 수 있으며, 시간 복잡도는 O(N²)입니다.