알고리즘 :: 백준 :: 시뮬레이션 :: 16926 :: 배열 돌리기1

문제

문제접근

문제 이해

• 알고리즘 :: 백준 :: 시뮬레이션 :: 16935 :: 배열 돌리기3 (velog.io) 문제와 이름은 동일하지만 배열 회전 방법이 완전히 다른 문제입니다.
• 회전 방식은 다음과 같습니다.
  • i번째 그룹은 a[i][i] 요소로 시작해서 시계방향으로 한 바퀴 돌 때 포함되는 모든 원소들을 포함합니다.
  • 회전은 각 i번째 그룹을 반시계방향으로 한 칸 이동하는 것을 의미합니다.

• 회전의 특성은 원소 개수만큼 회전을 하면 다시 원위치로 돌아온다는 점입니다.
  • 만일 원소가 5개 있는 일차원 배열이 있을 때
    • 왼쪽으로 5칸 회전시킨 배열은 원래 배열과 같습니다.
    • 왼쪽으로 13칸 회전시킨 배열은 왼쪽으로 3칸 회전시킨 배열과 같습니다.
    • 왼쪽으로 $N$칸 회전시킨 배열은 $N \ \% \ (원소개수)$칸 회전시킨 배열과 같습니다.
  • 이 특성을 이용해서 각 그룹의 원소 개수를 파악해 연산 회수를 대폭 감소할 수 있습니다.

해결 과정

1. 그룹들을 담을 2차원 배열을 만들고, 각 그룹은 1차원 배열에 넣습니다.
   이때 중복해서 넣는 것을 방지하기 위해 위 그림처럼 원소를 시계방향 순서로 넣습니다.
   • 넣는 방법은 저마다 다르므로 따로 설명하지 않겠습니다.
   • 저는 for문 4개를 써서 하나하나 넣었습니다.
2. 안쪽 i번째 그룹은 상,하,좌,우로 i - 1 칸씩 줄어드므로 고려해줍니다.
3. 각 그룹을 R % sizeof(group)번 회전합니다.
4. 그룹 배열에 넣었던 순서대로 다시 원소들을 배치합니다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, M, R;
	cin >> N >> M >> R;
	vector<vector<int>> a(N, vector<int>(M));
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			cin >> a[y][x];
			
	int ng = min(N, M) / 2;
	vector<vector<int>> groups;
    	// 그룹 배열에 각 그룹을 넣습니다.
	for (int g = 0; g < ng; ++g) {
		vector<int> group;
        int xmax = M - g - 1, ymax = N - g - 1;
		for (int x = g; x < xmax; ++x) group.push_back(a[g][x]);
		for (int y = g; y < ymax; ++y) group.push_back(a[y][xmax]);
		for (int x = xmax; x > g; --x) group.push_back(a[ymax][x]);
		for (int y = ymax; y > g; --y) group.push_back(a[y][g]);
		groups.push_back(group);
	}
    	// 회전시킨 뒤 원래 배열에 재배치합니다.
	for (int g = 0; g < ng; ++g) {
		vector<int> &group = groups[g];
		int len = group.size(), idx = R % len;
        	int xmax = M - g - 1, ymax = N - g - 1;
		for (int x = g; x < xmax; ++x, idx = (idx + 1) % len) a[g][x] = group[idx];
		for (int y = g; y < ymax; ++y, idx = (idx + 1) % len) a[y][xmax] = group[idx];
		for (int x = xmax; x > g; --x, idx = (idx + 1) % len) a[ymax][x] = group[idx];
		for (int y = ymax; y > g; --y, idx = (idx + 1) % len) a[y][g] = group[idx];
	}
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x)
			cout << a[y][x] << ' ';	
		cout << '\n';
	}
}

결과