반응형
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
알고리즘 종류
구현
완전탐색
사고 과정
최대 5번 이동이라고 하니 5번 이동해서 최대값을 찾습니다.
1. 이동방향은 순열조합으로 찾습니다.
2. 네 방향에 따라 이중 for문을 다르게 하여 블록을 이동시킵니다. 이동시키는 방법은 아래와 같습니다.
2-1) 범위 끝 또는 숫자가 있는 블록을 마주하면 한 칸 전으로 이동합니다.
2-2) 현재 한 칸 이전에 있는 상태입니다. 한 칸 앞에 블록이 있고 아직 합쳐지지 않았다면 합칩니다. 그 외의 경우에는 그대로 값을 놓습니다.
구현(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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
|
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n;
int ans = -1;
int selection[5]; // 회전을 저장할 배열
int mat[21][21]; // 원본
int cpy_mat[21][21]; // 복사본
int isMerged[21][21]; // 합쳐젔는지 확인하는 배열
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
bool isValid(int y, int x){
return (y>=0 && y<n) && (x>=0 && x<n);
}
void go(){
memcpy(cpy_mat, mat, sizeof(mat)); // 원본 복사
for(int idx=0; idx<5; idx++){
int d = selection[idx];
memset(isMerged, 0, sizeof(isMerged)); // 합쳐졌는지 확인하는 배열 초기화
if(d==0){
for(int y=n-2; y>=0; y--){
for(int x=0; x<n; x++){
if(cpy_mat[y][x] == 0) continue;
int ny = y;
int nx = x;
int data = cpy_mat[y][x];
// 블록 이동시키기
while(true){
ny += dir[d][0];
nx += dir[d][1];
if(cpy_mat[ny][nx] || !isValid(ny, nx)){
ny -= dir[d][0];
nx -= dir[d][1];
break;
}
}
cpy_mat[y][x] = 0;
// 도착할 블록이 같은 값을 가지고 아직 합쳐지지 않았으면 합체!
if(!isMerged[ny + dir[d][0]][nx + dir[d][1]]
&& cpy_mat[ny + dir[d][0]][nx + dir[d][1]] == data){
cpy_mat[ny + dir[d][0]][nx + dir[d][1]] += data;
isMerged[ny + dir[d][0]][nx + dir[d][1]] = 1;
}
else {
cpy_mat[ny][nx] = data;
}
}
}
}
else if(d==1){
for(int y=0; y<n; y++){
for(int x=n-2; x>=0; x--){
if(cpy_mat[y][x] == 0) continue;
int ny = y;
int nx = x;
int data = cpy_mat[y][x];
while(true){
ny += dir[d][0];
nx += dir[d][1];
if(cpy_mat[ny][nx] || !isValid(ny, nx)){
ny -= dir[d][0];
nx -= dir[d][1];
break;
}
}
cpy_mat[y][x] = 0;
if(!isMerged[ny + dir[d][0]][nx + dir[d][1]]
&& cpy_mat[ny + dir[d][0]][nx + dir[d][1]] == data){
cpy_mat[ny + dir[d][0]][nx + dir[d][1]] += data;
isMerged[ny + dir[d][0]][nx + dir[d][1]] = 1;
}
else {
cpy_mat[ny][nx] = data;
}
}
}
}
else if(d==2){
for(int y=1; y<n; y++){
for(int x=0; x<n; x++){
if(cpy_mat[y][x] == 0) continue;
int ny = y;
int nx = x;
int data = cpy_mat[y][x];
while(true){
ny += dir[d][0];
nx += dir[d][1];
if(cpy_mat[ny][nx] || !isValid(ny, nx)){
ny -= dir[d][0];
nx -= dir[d][1];
break;
}
}
cpy_mat[y][x] = 0;
if(!isMerged[ny + dir[d][0]][nx + dir[d][1]]
&& cpy_mat[ny + dir[d][0]][nx + dir[d][1]] == data){
cpy_mat[ny + dir[d][0]][nx + dir[d][1]] += data;
isMerged[ny + dir[d][0]][nx + dir[d][1]] = 1;
}
else {
cpy_mat[ny][nx] = data;
}
}
}
}
else if(d==3){
for(int y=0; y<n; y++){
for(int x=1; x<n; x++){
if(cpy_mat[y][x] == 0) continue;
int ny = y;
int nx = x;
int data = cpy_mat[y][x];
while(true){
ny += dir[d][0];
nx += dir[d][1];
if(cpy_mat[ny][nx] || !isValid(ny, nx)){
ny -= dir[d][0];
nx -= dir[d][1];
break;
}
}
cpy_mat[y][x] = 0;
if(!isMerged[ny + dir[d][0]][nx + dir[d][1]]
&& cpy_mat[ny + dir[d][0]][nx + dir[d][1]] == data){
cpy_mat[ny + dir[d][0]][nx + dir[d][1]] += data;
isMerged[ny + dir[d][0]][nx + dir[d][1]] = 1;
}
else {
cpy_mat[ny][nx] = data;
}
}
}
}
}
// 최대값 찾기
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(cpy_mat[i][j] > ans) ans = cpy_mat[i][j];
}
}
}
// 순열조합으로 방향 정하기
void dfs(int idx){
if(idx == 5){
go();
return;
}
for(int d=0; d<4; d++){
selection[idx] = d;
dfs(idx+1);
}
}
void solution(){
dfs(0);
cout << ans << endl;
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> mat[i][j];
}
}
solution();
}
|
cs |
시행착오
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
| [백준][C++] 1414 불우이웃돕기 (0) | 2021.04.11 |
|---|---|
| [백준][C++] 1368 물대기 (0) | 2021.04.11 |
| [백준][C++] 13460 구슬 탈출 2 (0) | 2021.04.10 |
| [백준][C++] 1445 일요일 아침의 데이트 (0) | 2021.04.10 |
| [백준][C++] 17780 새로운 게임 (0) | 2021.04.09 |