백준 16926 : 배열 돌리기 1

https://www.acmicpc.net/problem/16926

16926번: 배열 돌리기 1

 

배열을 돌리는 문제다. 다만 우리가 일반적으로 수학적으로 사용하는 행렬의 회전이 아니고 배열의 원소 하나하나를 문제에서 주어지는 특정한 횟수 R만큼 이동시킨다.

 

내가 문제를 해결한 과정은 아래와 같다.

1. 현재 배열의 가장 바깥쪽에 있는 행과 열(이하 배열의 가장자리)에 있는 원소들만 이동을 규칙에 맞게 이동시킨 후 배열의 가장자리를 제외한 내부의 배열에 대하여 다시 재귀적으로 작업을 수행한다.

2. 아래의 그림과 같이 배열의 가장자리를 총 4개의 케이스로 나누어 이동 작업을 수행한다. 케이스를 나눈 기준은 이동 방향이다.

3. 현재 배열의 가장자리에 포함되는 원소의 수만큼 이동하면 원래의 배열과 같다. 따라서 이동 횟수 R을 현재 배열의 가장자리에 포함되는 원소의 수로 나눈 나머지만큼 이동시킨다.

 

코드로 구현하면 아래와 같다.

#include <iostream>

#define min(a,b) a<b?a:b
using namespace std;

int n, m, r;
int board[300][300];
int rotated_board[300][300];

void move(int curx, int cury, int curr, const int& sx, const int& sy, const int& ex, const int& ey) {
	int init_x = curx;
	int init_y = cury;

	while (curr--) {
		//case 1
		if (cury == sy && curx != sx) --curx;
		//case 2
		else if (curx == sx && cury != ey) ++cury;
		//case 3
		else if (cury == ey && curx != ex) ++curx;
		//case 4
		else if (curx == ex && cury != sy) --cury;
	}

	rotated_board[cury][curx] = board[init_y][init_x];
}

void rotate(int offset) {
	int sx, sy, ex, ey, mod, cur_r;

	sx = offset, sy = offset;
	ex = m - offset, ey = n - offset;

	//기저 조건
	if ((min(ex - sx, ey - sy)) < 2) return;

	mod = 2 * (ex - sx) + 2 * (ey - sy) - 4;
	cur_r = r % mod;

	//마지막 인덱스에 위치시키기 위함
	--ex, --ey;

	//case 1
	for (int x = ex; x > sx; --x) move(x, sy, cur_r, sx, sy, ex, ey);
	//case 2
	for (int y = sy; y < ey; y++) move(sx, y, cur_r, sx, sy, ex, ey);
	//case 3
	for (int x = sx; x < ex; x++) move(x, ey, cur_r, sx, sy, ex, ey);
	//case 4
	for (int y = ey; y > sy; --y) move(ex, y, cur_r, sx, sy, ex, ey);

	rotate(offset + 1);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> r;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> board[y][x];
		}
	}

	rotate(0);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cout << rotated_board[y][x] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

메모리: 2724 kb

시간: 64 ms