[BOJ/Gold 3] 백준 20327 배열 돌리기 6(C++)

문제 링크

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

20327번: 배열 돌리기 6

크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분

www.acmicpc.net

문제

크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분 배열의 크기는 2ℓ×2ℓ가 되어야 한다. 단계는 연산을 수행할때마다 정한다.

다음은 크기가 23×23 배열을 단계 ℓ의 값에 따라 부분 배열로 나눈 것이다. 같은 부분 배열은 같은 색상으로 표시했다.

ℓ = 0ℓ = 1ℓ = 2

1번 연산은 각 부분 배열을 상하 반전시키는 연산이다.

배열ℓ = 1, 1번 연산 적용

2번 연산은 각 부분 배열을 좌우 반전시키는 연산이다.

배열ℓ = 2, 2번 연산 적용

3번 연산은 각 부분 배열을 오른쪽으로 90도 회전시키는 연산이다.

배열ℓ = 1, 3번 연산 적용

4번 연산은 각 부분 배열을 왼쪽으로 90도 회전시키는 연산이다.

배열ℓ = 2, 4번 연산 적용

5, 6, 7, 8번 연산은 부분 배열을 한 칸으로 생각하고 적용시킨다. 즉, 부분 배열의 안에 있는 값은 변하지 않는다.

5번 연산은 배열을 상하 반전시키는 연산이다.

배열ℓ = 2, 5번 연산 적용

6번 연산은 배열을 좌우 반전시키는 연산이다.

배열ℓ = 1, 6번 연산 적용

7번 연산은 오른쪽으로 90도 회전시키는 연산이다.

배열ℓ = 1, 7번 연산 적용

8번 연산은 왼쪽으로 90도 회전시키는 연산이다.

배열ℓ = 2, 8번 연산 적용

입력

첫째 줄에 N, R이 주어진다. 둘째 줄부터 2N개의 줄에 배열의 원소 A[i][j]가 주어진다. i번째 줄의 j번째 정수는 A[i][j]를 의미한다.

다음 R개의 줄에 배열에 적용시켜야 하는 연산이 한 줄에 하나씩 주어진다. 연산은 두 정수 k, ℓ로 이루어져 있고, k번 연산을 단계 ℓ로 적용한다는 의미이다.

출력

입력으로 주어진 배열에 R개의 연산을 순서대로 수행한 결과를 출력한다.

제한

1 ≤ N ≤ 7
1 ≤ R ≤ 1,000
1 ≤ k ≤ 8
0 ≤ ℓ < N
-999 ≤ A[i][j] ≤ 999

예제 입력 1

3 8
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 1
2 2
3 1
4 2
5 2
6 1
7 1
8 2

예제 출력 1

64 63 62 61 60 59 58 57
56 55 54 53 52 51 50 49
48 47 46 45 44 43 42 41
40 39 38 37 36 35 34 33
32 31 30 29 28 27 26 25
24 23 22 21 20 19 18 17
16 15 14 13 12 11 10 9
8 7 6 5 4 3 2 1

예제 입력 2

3 4
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 0
2 0
3 0
4 0

예제 출력 2

1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

예제 입력 3

3 4
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
5 0
6 0
7 0
8 0

예제 출력 3

64 63 62 61 60 59 58 57
56 55 54 53 52 51 50 49
48 47 46 45 44 43 42 41
40 39 38 37 36 35 34 33
32 31 30 29 28 27 26 25
24 23 22 21 20 19 18 17
16 15 14 13 12 11 10 9
8 7 6 5 4 3 2 1

예제 입력 4

3 8
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 2
8 1
7 2
4 0
3 2
5 1
6 1
2 2

예제 출력 4

45 37 47 39 41 33 43 35
46 38 48 40 42 34 44 36
61 53 63 55 57 49 59 51
62 54 64 56 58 50 60 52
13 5 15 7 9 1 11 3
14 6 16 8 10 2 12 4
29 21 31 23 25 17 27 19
30 22 32 24 26 18 28 20

알고리즘 분류

구현
시뮬레이션

풀이

다른 배열 돌리기보다 좀 많이 어려웠다. 그래서 다른 형님이 하신 것을 참고해서 풀었다.

https://conkjh032.tistory.com/287

[백준][C++] 20327 배열 돌리기 6

www.acmicpc.net/problem/20327 20327번: 배열 돌리기 6 크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열..

conkjh032.tistory.com

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 150
#define INF 1e9

using namespace std;
int N, Q;
int A_Size;
int A[MAX][MAX];

void First_Operation(int L) {
	int Cnt = 0;
	int tmp[MAX][MAX];
	for (int i = 0; i < A_Size; i++) {
		for (int j = 0; j < A_Size; j++) {
			tmp[i][j] = A[i][j];
		}
	}
	for (int i = 0; i < A_Size; i += L) {
		for (int j = 0; j < A_Size; j += L) {
			int Y = i;
			int X = j;
			for (int k = Y; k < (Y + L); k++) {
				for (int l = X; l < (X + L); l++) {
					A[Y + L - 1 - k + (L * Cnt)][l] = tmp[k][l];
				}
			}
		}
		Cnt++;
		/*
			1번 예제에서 (2, 0)을 좌우 반전하면 (3, 0)이 되는데,
			A[(Y + L - 1) - k][l] = (1, 0)이 되므로, L을 1번 더해주어야
			(3, 0)이 된다. 이 L을 몇 번 더할 건지는 Cnt라는 변수가 정해준다.
		*/
	}
}

void Second_Operation(int L) {
	int Cnt = 0;
	int tmp[MAX][MAX];
	for (int i = 0; i < A_Size; i++) {
		for (int j = 0; j < A_Size; j++) {
			tmp[i][j] = A[i][j];
		}
	}
	for (int i = 0; i < A_Size; i += L) {
		for (int j = 0; j < A_Size; j += L) {
			int Y = i;
			int X = j;
			for (int k = Y; k < (Y + L); k++) {
				for (int l = X; l < (X + L); l++) {
					A[k][X + L - 1 - l + (L * Cnt)] = tmp[k][l];
				}
			}
			Cnt++;
		}
		Cnt = 0;
	}
}

void Third_Operation(int L) {
	int R = 0, C = 0, Cnt = 0;
	int tmp[MAX][MAX];
	for (int i = 0; i < A_Size; i++) {
		for (int j = 0; j < A_Size; j++) {
			tmp[i][j] = A[i][j];
		}
	}
	for (int i = 0; i < A_Size; i += L) {
		for (int j = 0; j < A_Size; j += L) {
			int Y = i;
			int X = j;
			for (int k = Y; k < (Y + L); k++) {
				for (int l = X; l < (X + L); l++) {
					A[l - (L * R) + (L * Cnt)][Y + L - 1 - k + (L * C)] = tmp[k][l];
				}
			}
			R++;
			C++;
		}
		Cnt++;
		R = 0;
		C = 0;
		/*
			마찬가지로 R, C라는 변수를 이용해서 범위 안에서만 회전하도록 해준다.
		*/
	}
}

void Fourth_Operation(int L) {
	int R = 0, C = 0, Cnt = 0;
	int tmp[MAX][MAX];
	for (int i = 0; i < A_Size; i++) {
		for (int j = 0; j < A_Size; j++) {
			tmp[i][j] = A[i][j];
		}
	}
	for (int i = 0; i < A_Size; i += L) {
		for (int j = 0; j < A_Size; j += L) {
			int Y = i;
			int X = j;
			for (int k = Y; k < (Y + L); k++) {
				for (int l = X; l < (X + L); l++) {
					A[X + L - 1 - l + (L * R)][k + (L * C) - (L * Cnt)] = tmp[k][l];
				}
			}
			C++;
		}
		Cnt++;
		R++;
		C = 0;
	}
}

void Fifth_Operation(int L) {
	First_Operation(A_Size); // 전체를 상하반전
	First_Operation(L); // 이후 부분만 다시 상하반전시킨다.
	// 결과적으로 부분을 유지한 채로 전체가 상하반전된다.
}

void Sixth_Operation(int L) {
	Second_Operation(A_Size); // 전체를 좌우반전
	Second_Operation(L); // 이후 부분만 다시 좌우반전시킨다.
	// 결과적으로 부분을 유지한 채로 전체가 좌우반전된다.
}

void Seventh_Operation(int L) {
	Third_Operation(A_Size); // 전체를 시계방향 90도 회전
	Fourth_Operation(L); // 이후 부분만 다시 반시계 방향으로 90도 회전
	// 결과적으로 부분을 유지한 채로 전체가 시계방향으로 90도 회전된다.
}

void Eighth_Operation(int L) {
	Fourth_Operation(A_Size); // 전체를 반시계방향 90도 회전
	Third_Operation(L); // 이후 부분만 다시 시계 방향으로 90도 회전
	// 결과적으로 부분을 유지한 채로 전체가 반시계방향으로 90도 회전된다.
}

int main() {
	FIRST
	cin >> N >> Q;
	A_Size = (1 << N);
	for (int i = 0; i < A_Size; i++) {
		for (int j = 0; j < A_Size; j++) {
			cin >> A[i][j];
		}
	}
	for (int i = 0; i < Q; i++) {
		int K, L;
		cin >> K >> L;
		int Len = (1 << L);
		if (K == 1) {
			First_Operation(Len);
		}
		else if (K == 2) {
			Second_Operation(Len);
		}
		else if (K == 3) {
			Third_Operation(Len);
		}
		else if (K == 4) {
			Fourth_Operation(Len);
		}
		else if (K == 5) {
			Fifth_Operation(Len);
		}
		else if (K == 6) {
			Sixth_Operation(Len);
		}
		else if (K == 7) {
			Seventh_Operation(Len);
		}
		else if (K == 8) {
			Eighth_Operation(Len);
		}
	}
	for (int i = 0; i < A_Size; i++) {
		for (int j = 0; j < A_Size; j++) {
			cout << A[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

'BOJ > Gold' 카테고리의 다른 글

[BOJ/Gold 4] 백준 16722 결! 합!(C++) (0)	2022.01.16
[BOJ/Gold 3] 백준 23288 주사위 굴리기 2(C++) (0)	2022.01.15
[BOJ/Gold 3] 백준 18808 스티커 붙이기(C++) (0)	2022.01.13
[BOJ/Gold 3] 백준 17822 원판 돌리기(C++) (0)	2022.01.13
[BOJ/Gold 3] 백준 16986 인싸들의 가위바위보(C++) (0)	2022.01.12

문제 링크

문제

입력

출력

제한

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

알고리즘 분류

풀이

코드

'BOJ > Gold' 카테고리의 다른 글

티스토리툴바