[C] 2차원 배열 회전하기

대학교 1학년 시절(바야흐로 4년 전...) C프로그래밍 과제 문제 중에 하나인데 이때 당시 뻘짓이 인상적이어서 백업해 놓을 겸 올려놓는다.

아마 열혈C 도전 문제였던 걸로 기억하는데 문제 내용은 별거 아니었다. 그냥 아래처럼 4x4 배열을 시계방향으로 90도씩 회전시켜서 출력하는 것.

1	2	3	4	→	13	9	5	1	→	16	15	14	13	→	4	8	12	16
5	6	7	8		14	10	6	2		12	11	10	9		3	7	11	15
9	10	11	12		15	11	7	3		8	7	6	5		2	6	10	14
13	14	15	16		16	12	8	4		4	3	2	1		1	5	9	13

그냥 배열을 출력할 때 순서를 바꿔서 출력하는 식으로 쉽게 풀어도 되지만 이때 당시 나는 배열 자체를 회전시키는 거로 접근했다.

먼저 배열의 각 요소가 어떻게 이동하는지 살펴봤다.

(0,0) → (0,3)
(0,1) → (1,3)
(0,2) → (2,3)
(0,3) → (3,3)
(1,0) → (0,2)
(1,1) → (1,2)
(1,2) → (2,2)
(1,3) → (3,2)
(2,0) → (0,1)
(2,1) → (1,1)
(2,2) → (2,1)
(2,3) → (3,1)
(3,0) → (0,0)
(3,1) → (1,0)
(3,2) → (2,0)
(3,3) → (3,0)

규칙이 바로 보인다. (m,n) → (n,3-m)

이제 임시 배열 하나 만들어서 거기에 대입하면 되겠지만 나는 쓸데없는 메모리 낭비라는 생각이 들어서 처음 배열 안에서 자리를 바꾸는 방법을 생각했다. 하나의 자리를 바꾸면 연쇄적으로 자리가 바뀌므로 이를 정리하면 아래와 같다.

(0,0) → (0,3)
(0,3) → (3,3)
(3,3) → (3,0)
(3,0) → (0,0)

(0,1) → (1,3)
(1,3) → (3,2)
(3,2) → (2,0)
(2,0) → (0,1)

(0,2) → (2,3)
(2,3) → (3,1)
(3,1) → (1,0)
(1,0) → (0,2)

(1,1) → (1,2)
(1,2) → (2,2)
(2,1) → (1,1)
(2,2) → (2,1)

총 네 덩어리로 나뉘었는데 이번에도 규칙이 보인다.

(m,n) → (n,3-m)
(n,3-m) → (3-m,3-n)
(3-m,3-n) → (3-n,m)
(3-n,m) → (m,n)

여기까지만 했어도 충분한데 갑자기 4x4 배열뿐만 아니라 모든 nxn 배열에서 작동하게 만들고 싶어졌다. (뻘짓의 시작...)

일단 모든 nxn 배열에서 작동하려면 n의 값에 따라 반복 횟수가 바뀌어야 한다. 먼저 위 규칙을 일반화하기 위해 5x5 배열일 때를 생각해보았다.

(0,0) → (0,4)
(0,4) → (4,4)
(4,4) → (4,0)
(4,0) → (0,0)

(0,1) → (1,4)
(1,4) → (4,3)
(4,3) → (3,0)
(3,0) → (0,1)

(0,2) → (2,4)
(2,4) → (4,2)
(4,2) → (2,0)
(2,0) → (0,2)

(0,3) → (3,4)
(3,4) → (4,1)
(4,1) → (1,0)
(1,0) → (0,3)

(1,1) → (1,3)
(1,3) → (3,3)
(3,3) → (3,1)
(3,1) → (1,1)

(1,2) → (2,3)
(2,3) → (3,2)
(3,2) → (2,1)
(2,1) → (1,2)

이제 일반화하면 NxN 배열일 때

(m,n) → (n,N-m-1)
(n,N-m-1) → (N-m-1,N-n-1)
(N-m-1,N-n-1) → (N-n-1,m)
(N-n-1,m) → (m,n)

각 덩어리의 첫째 항끼리의 규칙성을 찾아서 for 문을 만들어야 하는데 감이 오지 않는다. (아마 이 부분에서 시간이 엄청나게 걸렸을 거다)

감이 잡히지 않아 6x6 배열도 생각해보았다. (길어서 각 덩어리의 첫째 항만 적음)

(0,0) → (0,5)
(0,1) → (1,5)
(0,2) → (2,5)
(0,3) → (3,5)
(0,4) → (4,5)
(1,1) → (1,4)
(1,2) → (2,4)
(1,3) → (3,4)
(2,2) → (2,3)

이제서야 규칙이 대강 보인다.

for (i = 0; i < size / 2; i++)
{
	for (j = i; j < size - i - 1; j++)
	{
		tmp = arr[size - j - 1][i];
		arr[size - j - 1][i] = arr[size - i - 1][size - j - 1];
		arr[size - i - 1][size - j - 1] = arr[j][size - i - 1];
		arr[j][size - i - 1] = arr[i][j];
		arr[i][j] = tmp;
	}
}

드디어 완성했다.

이다음 내용은 배열 매개변수 관련 내용이다. 내가 C를 배우면서 항상 불만이었던 부분이 매개변수로 배열을 넘기는 부분이다. (이후에 자바나 C# 등 다른 언어를 배우면서 더욱 체감됐다.) 배열을 넘길 때마다 크기를 따로 넘겨줘야 한다. 여기까진 그렇다 쳐도 이차원 배열은 넘겨줄 때부터 괴랄하다...

이 과제를 하면서 이차원 배열을 출력하는 부분을 만들어야 했는데 크기가 고정된 배열 말고 어떤 이차원 배열이든 자유롭게 출력하는 함수를 만들려니까 약간의 꼼수가 필요했다.

일단 일반적인 방법으로 만들면 이런 식이다.

void show2arr(int (*arr)[4], int row)
{
	int i, j;
	for (i = 0; i < row; i++)
	{
		for (j = 0; j < 4; j++)
		{
			printf("%3d ", arr[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

근데 이러면 열의 길이가 4로 고정되어 버린다. 이 문제를 해결하려고 생각해보니 몇 차원 배열이든 메모리상에는 일렬로 배치된다는 사실 생각났다.

void show2arr(int *arr, int row, int col)
{
	int i, j;
	for (i = 0; i < row; i++)
	{
		for (j = 0; j < col; j++)
		{
			printf("%3d ", arr[col * i + j]);
		}
		printf("\n");
	}
	printf("\n");
}

이차원 배열을 일차원 포인터로 받고 접근하는 방식인데 과제를 풀 당시 비주얼 스튜디오에선 문제가 없었으나 글을 쓰는 지금 gcc에서 테스트해보니 포인터 타입을 변환할 수 없다는 오류가 뜬다.

void show2arr(void *arr, int row, int col)
{
	int i, j;
	for (i = 0; i < row; i++)
	{
		for (j = 0; j < col; j++)
		{
			printf("%3d ", ((int *)arr)[col * i + j]);
		}
		printf("\n");
	}
	printf("\n");
}

그래서 어떤 포인터든 받을 수 있는 void 포인터를 사용하도록 수정했다.

이제 완성된 전체 소스코드는 아래와 같다.

#include <stdio.h>

void show2arr(void *arr, int row, int col)
{
	int i, j;
	for (i = 0; i < row; i++)
	{
		for (j = 0; j < col; j++)
		{
			printf("%3d ", ((int *)arr)[col * i + j]);
		}
		printf("\n");
	}
	printf("\n");
}

int main(void)
{
	int arr[4][4];	// 모든 정사각형 배열에서 작동함
	int size, i, j, tmp;

	size = sizeof(arr) / sizeof(arr[0]);
	for (i = 0; i < size; i++)
	{
		for (j = 0; j < size; j++)
		{
			arr[i][j] = size * i + j + 1;	// 배열 초기화
		}
	}
	show2arr(arr, size, size);

	for (i = 0; i < size / 2; i++)
	{
		for (j = i; j < size - i - 1; j++)
		{
			tmp = arr[size - j - 1][i];
			arr[size - j - 1][i] = arr[size - i - 1][size - j - 1];
			arr[size - i - 1][size - j - 1] = arr[j][size - i - 1];
			arr[j][size - i - 1] = arr[i][j];
			arr[i][j] = tmp;
		}
	}
	show2arr(arr, size, size);

	for (i = 0; i < size / 2; i++)
	{
		for (j = i; j < size - i - 1; j++)
		{
			tmp = arr[size - j - 1][i];
			arr[size - j - 1][i] = arr[size - i - 1][size - j - 1];
			arr[size - i - 1][size - j - 1] = arr[j][size - i - 1];
			arr[j][size - i - 1] = arr[i][j];
			arr[i][j] = tmp;
		}
	}
	show2arr(arr, size, size);

	for (i = 0; i < size / 2; i++)
	{
		for (j = i; j < size - i - 1; j++)
		{
			tmp = arr[size - j - 1][i];
			arr[size - j - 1][i] = arr[size - i - 1][size - j - 1];
			arr[size - i - 1][size - j - 1] = arr[j][size - i - 1];
			arr[j][size - i - 1] = arr[i][j];
			arr[i][j] = tmp;
		}
	}
	show2arr(arr, size, size);

	return 0;
}

실행 결과