[ Rotate Matrix ] 2차원 배열 회전 알고리즘

안녕하세요? 수구리입니다.

이번 포스팅에서는 PS 문제에서 한 번쯤은 보았을법한 2차원 배열 회전에 대한 내용입니다.

구체적인 문제를 풀면서 내용을 정리하려고 하였으나 좀 더 자주 쓰이는 내용일 것 같아서 따로 정리를 하는 글로 작성하게 되었습니다!

 

우선 간단하게 바로 5 X 5의 2차원 배열이 존재한다고 생각해보고,

시계방향으로 90도를 회전한다고 하였을 때 아래와 같은 그림입니다.

90도 회전

위의 그림에서 알 수 있는 부분은 90도 회전에서는 1행이 5열로 이동, 2행이 4열로 이동, 4행이 3열로 이동..

따라서 정리 index(row, col)를 정리하면 아래와 같습니다.

(0,0), (0,1), (0,2),... , (0,4)  => (0,4), (1,4), (2,4),... (4,4)

규칙을 찾아내 보면, 다음과 같습니다.

회전 후의 행(row) index는 기존 열 index가 됩니다.
회전 후의 열(col) index는 기존 행, 열 마지막 index(4)에서 기존 행 index(0)을 뺀 값이 됩니다.

위와 같은 규칙을 알 수 있습니다! 따라서 이를 코드로 표현해보도록 하겠습니다.

for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        temp[j][row-i-1] = mat[i][j];
    }
}

 

그렇다면 본격적으로 입력으로 N x M 짜리 행렬을 시계방향으로 90도 회전을 시켜보도록 하겠습니다.

이전에 Global 변수로 2차원 배열을 표현하기 위해서 mat과 temp라는 이중 포인터를 사용한 변수를 선언하였습니다.

Global 변수

int **mat;
int **temp;

 

그다음으로는 main 함수 부분입니다.

main 함수

int main() {
	int N, M, maxVal;

	cin >> N >> M;

	maxVal = max(N, M);

	mat = new int*[maxVal];
	for (int i = 0; i < maxVal; i++) {
		mat[i] = new int[maxVal];
		for (int j = 0; j < maxVal; j++) {
			mat[i][j] = (i*maxVal + j) + 1;
		}
	}

	cout << "----- Init Print mat -----\n";
	print(N, M, mat);

	rotateMat(N, M, mat);

	system("pause");
}

우선 visual studio 2015에서 콘솔 기반 응용 프로그램 프로젝트로 설정을 해주었습니다.

가장 먼저 N과 M 이후 row, col이 될 입력값을 받아옵니다.

이후, N과 M 중 <algorithm> 헤더의 max 함수를 사용해서 최댓값을 가져옵니다.

그 이유는 직사각형일 때를 대비해서입니다.

직사각형일 경우 위에서 소개한 Logic은 같지만, 기존 2차원 배열과 회전시킨 temp 배열의 크기(가로 x 세로)가 달라지므로 입력으로 받은 row와 col의 최댓값으로 기존 2차원 배열의 공간을 만들어 주기 위해서입니다. 

그다음으로 이중 for문을 통해서 동적 할당을 통해 2차원 배열 mat의 공간을 할당합니다. 2차원 배열에 값은 1부터 1씩 증가하는 값으로 초기화를 해주었습니다. 

아래는 print 함수입니다.

print 함수

void print(int n,int m, int** mat) {

	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < m; j++)	{
			if (mat[i][j] > 0 && mat[i][j] != NULL)
				cout << mat[i][j] << "\t";
		}
		cout << "\n";
	}
}

2차원 배열을 인자로 받아와 2중 for문을 통해 단순히 값을 출력하는 부분입니다.

배열 내부의 값이 0보다 크고 NULL이 아니면 출력합니다.

여기까지 위의 print 함수를 통해 테스트를 진행해보면 아래와 같습니다.

N이 3, M이 4인 2차원 배열이 잘 만들어졌네요.

 

다음으로는 90도 회전을 위해 rotateMat(N, M, mat)이라는 함수에 첫 번째 인자로 N, 두 번째 인자로 M, 그리고 초기화 한 mat 2차원 배열을 넘겨줍니다.

 

아래의 코드는 rotateMat 함수의 구현입니다.

rotateMat 함수

void rotateMat(int row, int col, int ** mat) {
	int tmpSize = max(row, col);

	// new temp
	temp = new int*[tmpSize];
	for (int i = 0; i < tmpSize; i++) {
		temp[i] = new int[tmpSize];
	}

	// temp 시계방향 90도 회전
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			temp[j][row-i-1] = mat[i][j];
		}
	}
	
	cout << "----- After 90 degree rotate -----\n";
	print(tmpSize, tmpSize, temp);

	// copy data from temp to mat
	for (int i = 0; i < tmpSize; i++) {
		for (int j = 0; j < tmpSize; j++) {
			if (temp[i][j] > 0)
				mat[i][j] = temp[i][j];
			else
				mat[i][j] = NULL;
		}
	}

	cout << "----- After Copy [temp -> mat] ----- \n";
	print(tmpSize, tmpSize, mat);

	// delete temp
	for (int i = 0; i < tmpSize; i++)
		delete[] temp[i];
	delete[] temp;

}

 

간략하게 설명을 하자면 새로운 2차원 배열 공간 temp를 만들어줍니다. 아까 mat 배열을 만드는 것과 동일합니다.

그 뒤로 90도 회전을 시킨 후, temp에는 초기 배열 mat이 90도 회전한 결과가 저장됩니다.

이후 copy 하는 부분에서는 temp의 값을 기존 2차원 배열인 mat으로 복사하는 부분인데요.

여기서 공간에 값이 제대로 들어가 있는 것만 mat 배열에 다시 넣어주는 작업을 하였습니다.

마지막으로는 temp를 delete 해주는 부분입니다. 이중 포인터이므로 이중으로 delete를 해주어야 합니다.

 

실행 결과

5 x 5 실행 결과

4 x 5 실행 결과

 

시계방향으로 90도 회전하는 2차원 배열을 구현했으니 이를 이용해서 180도, 270도 또한 마찬가지로 쉽게

구현할 수 있겠죠? (180도는 90도 회전을 2번, 270도는 90도회전을 3번)

이상으로 2차원 배열 회전하기였습니다. 감사합니다.