[백준] 골드5 : (16926) 배열 돌리기 1

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

 

기존 입력을 담은 배열과 이 배열을 회전시킨 값을 저장할 배열을 선언한다.

 

배열은 테두리마다 회전을 각자 한다.

다음과 같이 2차원 배열이 있을 때, 배열을 회전시키면 초록 부분은 초록 부분끼리 회전하고, 붉은 부분은 붉은 부분끼리 회전한다.

즉, 배열의 회전은 각 테두리에게만 영향을 미친다.

 

 

먼저, 테두리의 개수를 구해야 한다.

이는 다음과 같이 구할 수 있다. min(N, M) / 2

 

다음과 같이, 가로/세로가 커져도 결국 회전시킬 테두리는 2개로 같다.

 

 

이제 테두리를 회전시켜야 하는데, 구현은 다음과 같다.

• 임의의 수 하나를 회전시킨다.
• 회전시킨 위치를 기준으로 한 바퀴를 회전시켜 주면 해당 테두리의 회전이 완료된다.

 

결국 각 테두리만 회전시켜 주면 되기 때문에, 각 테두리의 시작점은 { 0, 0 }, { 1, 1 }, { 2, 2 }...으로 동일하다.

이 좌측 상단 꼭짓점을 처음 회전시킬 임의의 수로 두고, 회전시킨 결과를 확인한다.

 

{ 0, 0 }의 1을 회전시켰을 때, 3의 위치로 이동했다고 하자.

그러면 이제 1의 위치부터 3의 위치로 하나씩 앞으로 이동하며 기존 배열과 치환해 주면 된다.

이러면, 모든 수에 대해서 회전을 계산할 필요 없이, 수 하나만 계산해 주면 된다.

 

 

이때, 회전된 배열은 기존 배열에서 값을 가져와야 하기 때문에, 배열을 회전할 때 두 배열의 회전값이 동일하도록 맞춰줘야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int Map[301][301]{};
int NewMap[301][301]{};

int N, M, R;

// 현재 회전 방향
enum class Dir
{
	DOWN = 0,
	RIGHT,
	UP,
	LEFT
};

// 회전 함수
void MovePos(int& y, int& x, const int i, const int Nn, const int Mm, Dir& dir)
{
	while (true)
	{
		if (dir == Dir::DOWN)
		{
			if (y + 1 >= Nn) dir = Dir::RIGHT;
			else { y++; return; };
		}

		if (dir == Dir::RIGHT)
		{
			if (x + 1 >= Mm) dir = Dir::UP;
			else { x++; return; }
		}

		if (dir == Dir::UP)
		{
			if (y - 1 < i) dir = Dir::LEFT;
			else { y--; return; }
		}

		if (dir == Dir::LEFT)
		{
			if (x - 1 < i) dir = Dir::DOWN;
			else { x--; return; }
		}
	}
}

void Rotate(int i)
{
	// 기존 테두리의 좌측 상단의 위치
	int Sy = i, Sx = i;

	// 회전된 테두리의 좌측 상단 위치
	int Cy = i, Cx = i;

	// 현재 테두리 기준 N, M값, 남은 회전 횟수
	// 테두리가 좁아질수록, 배열 반경도 줄여줘야 함
	int Nn = N - i, Mm = M - i, Cr = R;

	// 기존 위치 방향, 이동 위치 방향
	Dir PrevDir = Dir::DOWN, NextDir = Dir::DOWN;

	// 처음 한 칸을 회전 시킴
	while (Cr--)
	{
		// y 아래로 이동
		if (Cx == i && Cy + 1 < Nn) { Cy++; NextDir = Dir::DOWN; }

		// X 오른쪽 이동
		else if (Cy == Nn - 1 && Cx < Mm - 1) { Cx++; NextDir = Dir::RIGHT; }

		// y 위로 이동
		else if (Cx == Mm - 1 && Cy != i) { Cy--; NextDir = Dir::UP; }

		// x 왼쪽 이동
		else if (Cy == i && Cx != i) { Cx--; NextDir = Dir::LEFT; }
	}

	// 배열 회전이 끝날 위치 (회전이 모두 끝나고 자기 자리로 오면 종료)
	int Dy = Cy, Dx = Cx;

	NewMap[Cy][Cx] = Map[Sy][Sx];
	while (true)
	{
		MovePos(Cy, Cx, i, Nn, Mm, NextDir); // 현재 배열 회전
		MovePos(Sy, Sx, i, Nn, Mm, PrevDir); // 기존 배열 회전
		NewMap[Cy][Cx] = Map[Sy][Sx]; // 회전된 배열 초기화

		if (Cy == Dy && Cx == Dx) return;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> R;

	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			cin >> Map[y][x];

	// 정사각형이 만들어지는 개수
	int Min = min(N, M) / 2;

	// 배열 돌리기
	for (int i = 0; i < Min; ++i) Rotate(i);

	// 답 출력
	for (int y = 0; y < N; ++y)
	{
		for (int x = 0; x < M; ++x)
		{
			cout << NewMap[y][x];
			if (x < M - 1) cout << " ";
			else cout << "\n";
		}
	}
}