2차원 배열에서 90도 회전 알고리즘

2차원 배열에서 90도 회전하는 방법을 알아보자 😋

시계 방향 90도 회전

배열 전체를 회전

N * N 크기의 2차원 배열 전체를 시계방향으로 회전 시키는 방법은 생각보다 간단하다. 우선 이해를 돕기위해 1~25의 숫자를 가지는 5x5 크기의 2차원 배열을 그려 두었다. 회전 전후를 비교해서 보면 규칙성이 있는데, 바로 r 행이 5-1-r 열이 된다는 것이다. 또한, c 열을 r 행이 됨을 알 수 있다. (여기서 행과 열은 0부터 시작한다고 가정한다.) 이를 공식화해보면, arr[c][size-r-1] = arr[r][c]이 됨을 확인할 수 있다.

이를 코드로 작성하면 다음과 같다. 임시 배열을 하나 만들어서 그 곳에 90도로 시계방향한 상태를 저장해주었다. 이를 다시 기존 배열에 옮겨서 사용할 수 있다.

int arr[N][N], tmp_arr[N][N];

for(int i=0; i<N; i++){
	for(int j=0; j<N; j++) tmp_arr[j][N-1-i] = arr[i][j];
}

배열의 특정 구간을 회전

배열의 특정 구간을 회전하기 위해서는 앞선 공식을 그대로 이용하지만, 기준점, 즉, 회전하고자 하는 사각형의 좌측상단 - (y1, x1)만 더해주면된다.

이를 코드로 작성하면 다음과 같다.

void rotate_square(int y1, int x1) {
	int mid = n / 2;
	for (int i = 0; i < mid; i++) {
		for (int j = 0; j < mid; j++) tmp_arr[y1 + j][x1 + mid - i - 1] = arr[y1 + i][x1 + j];
	}
}

// 정사각형 시계 방향 90' 회전
int mid = n / 2;
rotate_square(0, 0); // 좌상
rotate_square(0, mid + 1); // 우상
rotate_square(mid + 1, 0); // 좌하
rotate_square(mid + 1, mid + 1); // 우하

반시계 방향 90도 회전

배열 전체를 회전

반시계 방향 또한 회전 전후를 비교해서 보면 규칙성이 있는데, 바로 c열이 5-1-c 행이 된다는 것이다. 또한, r 행은 c 열이 됨을 알 수 있다. 이를 공식화해보면, arr[size-c-1][r] = arr[r][c]이 됨을 확인할 수 있다.

이를 코드로 작성하면 다음과 같다.

int arr[N][N], tmp_arr[N][N];

for(int i=0; i<N; i++){
	for(int j=0; j<N; j++) tmp_arr[size-1-j][i] = arr[i][j];
}

배열의 특정 구간을 회전

시계방향에서 했던 것과 마찬가지로, 기준점, 즉, 회전하고자 하는 사각형의 좌측상단 - (y1, x1)만 더해주면된다.

이를 코드로 작성하면 다음과 같다.

void rotate_square(int y1, int x1) {
	int mid = n / 2;
	for (int i = 0; i < mid; i++) {
		for (int j = 0; j < mid; j++) TMP_MAP[y1 + mid - j - 1][x1 + i] = MAP[y1 + i][x1 + j];
	}
}

// 정사각형 반시계 방향 90' 회전
int mid = n / 2;
rotate_square(0, 0); // 좌상
rotate_square(0, mid + 1); // 우상
rotate_square(mid + 1, 0); // 좌하
rotate_square(mid + 1, mid + 1); // 우하