[BOJ] 16926번_배열 돌리기 1_구현 (C++)

[문제]

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

크기가 NxM인 배열이 있을 때, 배열을 돌리려고 한다. 배열은 다음과 같이 반시계 방향으로 돌아간다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변한다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구하는 문제이다.

[사용 알고리즘]

구현

[풀이 핵심]

• 사이클은 행과 열 중 작은 값의 절반 만큼 생긴다. ( min(N, M) / 2 )
  -> min(N, M) mod 2 = 0 이라는 조건이 있어서 홀수는 신경안써도 된다.
• 사이클은 위,오른쪽,왼쪽,아래로 나눠서 돌려준다. 위치마다 이동하는 방향이 다르기 때문이다.
• 먼저 사이클의 제일 왼쪽 위을 기준으로 잡고 위부터 돌려준다. (0,0 / 1,1 / 2,2 / ...) 첫 번째 사이클을 생각해보면 위쪽은 오른쪽에서 왼쪽으로 이동해야 되므로 0,1에 있는 수를 0,0으로 옮기는 식으로 돌려준다. (rot가 0이면 dy[rot], dy[rot]가 0,1이 된다.)
• 위와 같은 방식으로 사이클을 돌려주면서 prev_x나 prev_y가 사이클의 밖으로 나가면 방향을 바꾼다.
• 마지막으로 제일 마지막 칸에 0,0의 값을 넣어주는 것도 잊지말자.

[코드]

//boj16926번_배열 돌리기 1_구현

#include<iostream>

using namespace std;

int N, M, R;

int graph[301][301];

int dx[4] = {0,1,0,-1};
int dy[4] = { 1,0,-1,0 };

void rotate() {
	for (int i = 0; i < min(N, M) / 2; i++) {
		int x = i;
		int y = i;
		int rot = 0;

		int start = graph[i][i];

		while (rot < 4) {
			int prev_x = x + dx[rot];
			int prev_y = y + dy[rot];

			if (prev_x >= i && prev_x < N - i && prev_y >= i && prev_y < M - i) {
				graph[x][y] = graph[prev_x][prev_y];
				x = prev_x;
				y = prev_y;
			}
			else {
				rot++;
			}
		}
		graph[i + 1][i] = start;
	}
}

int main() {
	cin >> N >> M >> R;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> graph[i][j];
		}
	}

	for (int i = 0; i < R; i++) {
		rotate();
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << graph[i][j] << " ";
		}
		cout << '\n';
	}
}