<12100> 2048 (Easy)

문제 : https://www.acmicpc.net/problem/12100

째로탈출2처럼 코드가 깁니다… 째로탈출2와 마찬가지로 2차원 배열을 조작하는 부분에서 코드가 많이 길어지게 되는데 더 간결하게 만들 수 있도록 연습을 해야할 것 같습니다.
구현은 combine_map함수를 통해서 방향에 맞게 같은 숫자를 합쳐주고 move_map함수를 통해 빈공간을 제거하는것을 반복하도록 구현했습니다. Easy의 경우 5회 반복이기 때문에 대부분 시간초과 경우는 없을 것 입니다.
(테스트 케이스가 문제에 1개 밖에 없다보니 힘들었습니다… 테스트 케이스가 부족하신 분들은 문제 게시판에 가시면 더 찾아보실 수 있습니다.)

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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
#include <iostream>
#include <algorithm>

#define MAP_MAX_SIZE 20
using namespace std;

int map[MAP_MAX_SIZE][MAP_MAX_SIZE];
int N;
int max_dp[6];

void init_map() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
}

void copy_map(int(*map)[MAP_MAX_SIZE], int(*tmp_map)[MAP_MAX_SIZE]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
tmp_map[i][j] = map[i][j];
}
}
}

void recovery_map(int(*map)[MAP_MAX_SIZE], int(*tmp_map)[MAP_MAX_SIZE]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = tmp_map[i][j];
}
}
}

void combine_map(int dir) {
// 상
if (dir == 0) {
for (int c = 0; c < N; c++) {
for (int r = 0; r < N - 1; r++) {
int data1 = map[r][c];

if (data1 == 0) {
continue;
}

for (int k = r + 1; k < N; k++) {
int data2 = map[k][c];

if (data2 == 0) {
continue;
}
else {
if (data1 == data2) {
map[r][c] *= 2;
map[k][c] = 0;
r = k;
}
break;
}
}
}
}
}
// 하
else if (dir == 1) {
for (int c = 0; c < N; c++) {
for (int r = N-1; r > 0; r--) {
int data1 = map[r][c];

if (data1 == 0) {
continue;
}

for (int k = r - 1; k >= 0; k--) {
int data2 = map[k][c];

if (data2 == 0) {
continue;
}
else {
if (data1 == data2) {
map[r][c] *= 2;
map[k][c] = 0;
r = k;
}
break;
}
}
}
}
}
// 좌
else if (dir == 2) {
for (int r = 0; r < N; r++) {
for (int c = 0; c < N - 1; c++) {
int data1 = map[r][c];

if (data1 == 0) {
continue;
}

for (int k = c + 1; k < N; k++) {
int data2 = map[r][k];

if (data2 == 0) {
continue;
}
else {
if (data1 == data2) {
map[r][c] *= 2;
map[r][k] = 0;
c = k;
}
break;
}
}
}
}
}
// 우
else if (dir == 3) {
for (int r = 0; r < N; r++) {
for (int c = N-1; c > 0; c--) {
int data1 = map[r][c];

if (data1 == 0) {
continue;
}

for (int k = c - 1; k >= 0; k--) {
int data2 = map[r][k];

if (data2 == 0) {
continue;
}
else {
if (data1 == data2) {
map[r][c] *= 2;
map[r][k] = 0;
c = k;
}
break;
}
}
}
}
}
}

int move_map(int dir) {
int max_value = 0;

// 상
if (dir == 0) {
for (int c = 0; c < N; c++) {
for (int r = 0; r < N; r++) {
max_value = max(max_value, map[r][c]);

if (map[r][c] == 0 && r != N - 1) {
for (int k = r+1; k < N; k++) {
if (map[k][c] != 0) {
map[r][c] = map[k][c];
map[k][c] = 0;
max_value = max(max_value, map[r][c]);
break;
}
}
}
}
}
}
// 하
else if (dir == 1) {
for (int c = 0; c < N; c++) {
for (int r = N-1; r >= 0; r--) {
max_value = max(max_value, map[r][c]);

if (map[r][c] == 0 && r != 0) {
for (int k = r - 1; k >= 0; k--) {
if (map[k][c] != 0) {
map[r][c] = map[k][c];
map[k][c] = 0;
max_value = max(max_value, map[r][c]);
break;
}
}
}
}
}
}
//좌
else if (dir == 2) {
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
max_value = max(max_value, map[r][c]);

if (map[r][c] == 0 && c != N-1) {
for (int k = c + 1; k < N; k++) {
if (map[r][k] != 0) {
map[r][c] = map[r][k];
map[r][k] = 0;
max_value = max(max_value, map[r][c]);
break;
}
}
}
}
}
}
//우
else if (dir == 3) {
for (int r = 0; r < N; r++) {
for (int c = N-1; c >= 0; c--) {
max_value = max(max_value, map[r][c]);

if (map[r][c] == 0 && c != 0) {
for (int k = c - 1; k >= 0; k--) {
if (map[r][k] != 0) {
map[r][c] = map[r][k];
map[r][k] = 0;
max_value = max(max_value, map[r][c]);
break;
}
}
}
}
}
}

return max_value;
}

void dfs(int cnt, int max_value) {
max_dp[cnt] = max(max_dp[cnt], max_value);

if (cnt >= 5) {
return;
}

// 상, 하, 좌, 우
for (int dir = 0; dir < 4; dir++) {
int tmp_map[MAP_MAX_SIZE][MAP_MAX_SIZE];
copy_map(map, tmp_map);

combine_map(dir); // 기울인 방향으로 합치기
int value = move_map(dir); // 빈칸 땡기기 & 현재 최대값 반환
dfs(cnt + 1, value);

recovery_map(map, tmp_map);
}
}

int main() {
ios::sync_with_stdio(false);
cin >> N;

init_map();
dfs(0, 0);

cout << max_dp[5] << '\n';

return 0;
}

댓글

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×