반응형
16935번: 배열 돌리기 3
크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 →
www.acmicpc.net
알고리즘 종류
- 구현
사고 과정
- 주어진 6개의 명령에 따라 배열을 돌리면 된다.
0. n은 가로의 개수, m은 세로의 개수이다.
1. 상하반전 : row값이 i이면, 상하반전으로 놓일 곳은 n-1-i 이다.
2. 좌우반전 : column값이 j이면, 좌우반전으로 놓일 곳은 m-1-j이다.
3. 시계방향 90도 회전 : (i, j)의 값은, (j, n-1-i)에 위치하게 된다. 그리고 n과 m의 크기가 바뀐다.
4. 반시계방향 90도 회전 : (i, j)의 값은, (m-1-j, i)에 위치하게 된다. 그리고 n과 m의 크기가 바뀐다.
5. 구역 위치 옮김1 : 4개의 구역을 n/2, m/2을 사용해서 나누고 n/2와 m/2를 빼거나 더해서 위치를 바꾼다.
6. 구역 위치 옮김2 : 5번과 동일한 방법
구현(C++)
|
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, m, r;
int mat[101][101];
int mat2[101][101];
vector<int> v;
int how;
void print(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cout << mat[i][j] << " ";
}
cout << endl;
}
}
void upside_down(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
mat2[n-1-i][j] = mat[i][j];
}
}
memcpy(mat, mat2, sizeof(mat2));
}
void left_and_right_reverse(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
mat2[i][m-1-j] = mat[i][j];
}
}
memcpy(mat, mat2, sizeof(mat2));
}
void clockwise(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
mat2[j][n-i-1] = mat[i][j];
}
}
memcpy(mat, mat2, sizeof(mat2));
int tmp = n;
n = m;
m = tmp;
}
void counter_clockwise(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
mat2[m-1-j][i] = mat[i][j];
}
}
memcpy(mat, mat2, sizeof(mat2));
int tmp = n;
n = m;
m = tmp;
}
void change_location_1(){
for(int i=0; i<n/2; i++){
for(int j=0; j<m/2; j++){
mat2[i][j+m/2] = mat[i][j];
}
}
for(int i=0; i<n/2; i++){
for(int j=m/2; j<m; j++){
mat2[i+n/2][j] = mat[i][j];
}
}
for(int i=n/2; i<n; i++){
for(int j=m/2; j<m; j++){
mat2[i][j-m/2] = mat[i][j];
}
}
for(int i=n/2; i<n; i++){
for(int j=0; j<m/2; j++){
mat2[i-n/2][j] = mat[i][j];
}
}
memcpy(mat, mat2, sizeof(mat2));
}
void change_location_2(){
for(int i=0; i<n/2; i++){
for(int j=0; j<m/2; j++){
mat2[i+n/2][j] = mat[i][j];
}
}
for(int i=n/2; i<n; i++){
for(int j=0; j<m/2; j++){
mat2[i][j+m/2] = mat[i][j];
}
}
for(int i=n/2; i<n; i++){
for(int j=m/2; j<m; j++){
mat2[i-n/2][j] = mat[i][j];
}
}
for(int i=0; i<n/2; i++){
for(int j=m/2; j<m; j++){
mat2[i][j-m/2] = mat[i][j];
}
}
memcpy(mat, mat2, sizeof(mat2));
}
void solution(){
for(int i=0; i<v.size(); i++){
how = v[i];
if(how == 1) upside_down();
else if(how == 2) left_and_right_reverse();
else if(how == 3) clockwise();
else if(how == 4) counter_clockwise();
else if(how == 5) change_location_1();
else if(how == 6) change_location_2();
}
print();
}
int main(void){
cin >> n >> m >> r;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin >> mat[i][j];
//
for(int i=0; i<r; i++){
cin >> how;
v.push_back(how);
}
solution();
}
|
cs |
시행착오
- 시계방향, 반시계방향 90도 회전에 대해서 이해할 수 있는 문제였다.
- 구역을 나누어서 옮기는 방법에 대해서 이해할 수 있는 문제였다.
반응형