백준 - 16926 배열 돌리기 1

문제

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

16926번: 배열 돌리기 1

크기가 NxM인 배열을 한 줄씩 나눠서 R번 회전한 결과를 출력하는 문제였다.

 

문제 풀이

배열이 최대 300 x 300 크기고, 돌리는 횟수도 최대 1000번이라 실제로 다 돌려도 최대 90000000이어서 아슬아슬하게 제한 시간을 통과할 수는 있을 것 같았다. 하지만 다른 방법을 이용해 풀었다.

 

먼저 회전하는 네모 부분들을 한 줄로 저장했다.

회전하는 네모 부분들은 반시계 방향으로 회전하기 때문에 끝이 이어진 원형 배열로 생각할 수 있다.

벡터의 끝과 끝이 연결되었다고 가정하면 이를 하나의 벡터로 나타낼 수 있다.

이와 같은 네모 하나를 한 줄로 나타낸 벡터에서 R번 회전하는 것은 현재 위치에서 R 떨어져 있는 곳으로 각각의 요소를 이동시키는 것이 된다.

 

이때 N*M 크기의 배열에서 회전시키는 범위의 벡터의 수는 N/2과 M/2 중 작은 값 만큼,이때 N과 M이 둘 다 홀수면 1 더한만큼 생긴다.

 

입력받은 벡터를 하우상좌 순서대로 각 벡터에 저장하면 2차원 배열의 회전하는 부분들(네모 부분)의 값이 저장된 벡터들을 얻을 수 있다.

 

이 벡터의 각 요소를 모두 R만큼 옮기고, 이를 다시 이어붙인다면 원래의 배열이 R번 회전된 결과를 얻을 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M, R;
int map[305][305];
//하우상좌
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int startx;
int endx;
int starty;
int endy;

vector<int> rotation(vector<int> v) { //항상 반시계 방향으로 돌려야 함
	//v.size() 를 r로 나눈 나머지만큼 옮기기
	vector<int> resultV(v.size());

	for (int i = 0; i < v.size(); i++) {
		//i자리에 있는 원소를 (i+r)%r 위치로 옮기기
		resultV[(i + R) % v.size()] = v[i];
	}
	return resultV;
}

void printVector(vector<vector<int>> vec) {
	for (vector<int> v : vec) {
		for (int n : v) {
			printf("%d ", n);
		}
		printf("\n");
	}
	printf("\n");
}

bool isInside(int x, int y) {
	if (x >= startx && x <= endx && y >= starty && y <= endy) return true;
	return false;
}

int main(int argc, char** argv)
{
	scanf("%d %d %d", &N, &M, &R);

	int vectorSize = min(N / 2, M / 2);

	if (N % 2 == 1 && M % 2 == 1) vectorSize++;
	vector<vector<int>> arr(vectorSize);

	//입력받기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	int size = 2 * N + 2 * M - 4;
	//arr에서 네모들을 각각 하나의 vector 한 줄로 저장하기
	for (int k = 1; k <= vectorSize; k++) {
		startx = k - 1;
		endx = N - k;
		starty = k - 1;
		endy = M - k;

		int dir = 0;
		int x = startx;
		int y = starty;
		for (int i = 0; i < size; i++) {
			arr[k - 1].push_back(map[x][y]);
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (!isInside(nx, ny)) { //방향 바꿔줘야함
				dir++;
				dir %= 4;

				nx = x + dx[dir];
				ny = y + dy[dir];
			}
			x = nx;
			y = ny;
		}
		size = (N - (k * 2)) * 2 + (M - (k * 2)) * 2 - 4;
	}

	//printVector(arr);

	for (int i = 0; i < vectorSize; i++) {
		arr[i] = rotation(arr[i]);
	}

	//printVector(arr);

	//map의 요소를 arr 요소대로 채우기
	size = 2 * N + 2 * M - 4;
	for (int k = 1; k <= vectorSize; k++) {
		startx = k - 1;
		endx = N - k;
		starty = k - 1;
		endy = M - k;

		int dir = 0;
		int x = startx;
		int y = starty;
		for (int i = 0; i < size; i++) {
			map[x][y] = arr[k - 1][i];
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (!isInside(nx, ny)) { //방향 바꿔줘야함
				dir++;
				nx = x + dx[dir];
				ny = y + dy[dir];
			}
			x = nx;
			y = ny;
		}
		size = (N - (k * 2)) * 2 + (M - (k * 2)) * 2 - 4;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
	return 0;
}