카테고리 없음
[백준][17406] 배열 돌리기 4
김 정 환
2021. 2. 2. 16:11
반응형
알고리즘 종류
- 구현
- 브루트포스
사고 과정
1. 순열조합을 이용해서 회전 연산 경우의 수 구하기
2. 구해진 경우에 따라 배열 회전시키기
- 그림 설명
* 좌측상단의 값을 tmp에 임시로 저장한다.
* 4면의 배열을 옮긴다.
* 다 옮기면 아래처럼 노란색 배열이 비게 된다. tmp의 값을 넣어준다.
* 가장자리의 이동은 끝났으니 안으로 들어온다. 안쪽도 위에서 했던 동작 그대로 이행한다. 빨간색 박스가 중심에 도착할 때까지 이 과정을 반복한다.
구현(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
|
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, m, k;
int answer = 987654321;
int mat[51][51];
int mat2[51][51];
int isSelected[7];
vector<vector<int> > v;
vector<int> order;
void rotation(){
memcpy(mat2, mat, sizeof(mat));
// 조합된 경우의 수에 따라 회전시키기
// 예시)
// 회전 연산이 2개 (1과 2)가 있을 경우, {1, 2}, {2, 1}의 경우가 있다.
// 여기서 {1, 2}를 사용하여 회전시킨다.
for(int i=0; i<k; i++){
// order 벡터에 저장된 회전 연산 번호를 가져온다.
// order 벡터에는 회전 연산의 적용 순서가 들어있다.
// 위 예시로 말하자면, {1, 2}가 들어있다.
int seq = order[i];
// 회전 연산의 정보가 저장된 벡터에서 r, c, s의 값을 가져온다.
int y = v[seq][0];
int x = v[seq][1];
int s = v[seq][2];
// 시작점을 잡는다. 시작점은 좌측상단이다.
int sy = y-s, sx = x-s;
// 정사각형 변에서 움직일 거리
int len = 2*s;
while(true){
// 값 하나를 빼온다.
int tmp = mat2[sy][sx];
// 왼쪽 배열을 아래에서 위로 옮긴다.
for(int j=0; j<len; j++){
mat2[sy][sx] = mat2[sy+1][sx];
sy++;
}
// 아래쪽 배열을 왼쪽으로 옮긴다.
for(int j=0; j<len; j++){
mat2[sy][sx] = mat2[sy][sx+1];
sx++;
}
// 오른쪽 배열을 아래로 옮긴다.
for(int j=0; j<len; j++){
mat2[sy][sx] = mat2[sy-1][sx];
sy--;
}
// 위쪽 배열을 오른쪽으로 옮긴다.
for(int j=0; j<len-1; j++){
mat2[sy][sx] = mat2[sy][sx-1];
sx--;
}
// 다 옮긴 후 빈 곳에 넣는다.
mat2[sy][sx] = tmp;
// 시작점으로 옮긴다.
sx--;
// 우측하단으로 +1 만큼씩 움직인다.
sy = sy + 1;
sx = sx + 1;
// 배열에서 움직일 거리는 2가 줄어든다.
len = len - 2;
// 우측하단으로 옮겼는데, 중심을 지날 경우에는 회전할 필요가 없으므로 종료
if(sy >= y && sx >= x) break;
}
}
// 행의 값을 구하여 최소값을 갱신한다.
for(int i=1; i<=n; i++){
int total = 0;
for(int j=1; j<=m; j++){
total += mat2[i][j];
}
answer = min(answer, total);
}
}
void combination(int cnt){
// 순열조합이 완료되면, 배열을 회전시킨다.
if(cnt == k){
rotation();
return;
}
// 여기서는 순서가 상관있다. {1, 3}과 {3, 1}은 다른 결과를 만든다.
// order 벡터에 회전 연산의 번호를 넣는다.
for(int i=0; i<k; i++){
if(isSelected[i]) continue;
isSelected[i] = 1;
order.push_back(i);
combination(cnt+1);
order.pop_back();
isSelected[i] = 0;
}
}
void solution(){
// dfs로 순열조합을 구한다.
combination(0);
cout << answer << endl;
}
int main(void){
cin >> n >> m >> k;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin >> mat[i][j];
}
}
// 회전 연산을 저장한다.
for(int i=0; i<k; i++){
vector<int> tmp_v;
for(int j=0; j<3; j++){
int num;
cin >> num;
tmp_v.push_back(num);
}
v.push_back(tmp_v);
}
solution();
}
|
cs |
시행착오
- 회전 문제는 항상 고민이었다. 어떻게 해결해야 할까. 이전에는 회전 공식을 이용해서 풀었었다. sin과 cos을 이용했었다. 여기서 사용한 방법은 중심에 배열이 있을 때 회전하기 괜찮은 방법으로 보인다. 반시계 방향도 할 수 있게 적용할 수 있을 것 같다.
반응형