dfs라는 함수를 통하여 0의 자리를 전부 채우고 방향에 따라 이동시켜준다.
그 후 checkmax() 를통하여 res변수를 업데이트해주어 문제가 원하는 값을 얻게끔 코딩하였다.
조금 더 생각해봐야겠지만 아직 시간을 더 줄일수 있는 방법을 찾지 못했다.
https://github.com/ukjinlee66/BOJ/blob/master/12100.cpp
ukjinlee66/BOJ
baekjoon. Contribute to ukjinlee66/BOJ development by creating an account on GitHub.
github.com
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
|
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
|
#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int res;
int ar[22][22];
int br[22][22];
int checkmax()
{
int re = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
re = max(re, ar[i][j]);
}
return re;
}
void dfs(int num, int cnt = 0)
{
int cr[22][22] = { 0 };
if (cnt == 5)
{
res = max(res, checkmax());
return;
}
if (num == 0) //up
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (ar[j][i] == 0) //(1) 0인 자리를전부채움.
{
for (int k = j + 1; k <= n; k++)
{
if (ar[k][i] != 0)
{
ar[j][i] = ar[k][i];
ar[k][i] = 0;
break;
}
}
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (ar[j][i] == ar[j + 1][i])
{
ar[j][i] = ar[j][i] * 2;
ar[j + 1][i] = 0;
for (int k = j + 1; k <= n - 1; k++)
{
ar[k][i] = ar[k + 1][i];
ar[k + 1][i] = 0;
}
}
}
}
}
else if (num == 1)//left
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (ar[i][j] == 0) //(1) 0인 자리를전부채움.
{
for (int k = j + 1; k <= n; k++)
{
if (ar[i][k] != 0) {
ar[i][j] = ar[i][k];
ar[i][k] = 0;
break;
}
}
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (ar[i][j] == ar[i][j + 1])
{
ar[i][j] = ar[i][j] * 2;
ar[i][j + 1] = 0;
for (int k = j + 1; k <= n - 1; k++)
{
ar[i][k] = ar[i][k + 1];
ar[i][k + 1] = 0;
}
}
}
}
}
else if (num == 2)//right
{
for (int i = 1; i <= n; i++)
{
for (int j = n; j >= 1; j--)
{
if (ar[i][j] == 0) //(1) 0인 자리를전부채움.
{
for (int k = j - 1; k >= 1; k--)
{
if (ar[i][k] != 0) {
ar[i][j] = ar[i][k];
ar[i][k] = 0;
break;
}
}
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = n; j >= 1; j--)
{
if (ar[i][j] == ar[i][j - 1])
{
ar[i][j] = ar[i][j] * 2;
ar[i][j - 1] = 0;
for (int k = j - 1; k >= 2; k--)
{
ar[i][k] = ar[i][k - 1];
ar[i][k - 1] = 0;
}
}
}
}
}
else if (num == 3)//down
{
for (int i = 1; i <= n; i++)
{
for (int j = n; j >= 1; j--)
{
if (ar[j][i] == 0) //(1) 0인 자리를전부채움.
{
for (int k = j - 1; k >= 1; k--)
{
if (ar[k][i] != 0) {
ar[j][i] = ar[k][i];
ar[k][i] = 0;
break;
}
}
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = n; j >= 1; j--)
{
if (ar[j][i] == ar[j - 1][i])
{
ar[j][i] = ar[j][i] * 2;
ar[j - 1][i] = 0;
for (int k = j - 1; k >= 2; k--)
{
ar[k][i] = ar[k - 1][i];
ar[k - 1][i] = 0;
}
}
}
}
}
for (int i = 0; i < 4; i++)
{
memcpy(cr, ar, sizeof(ar));
dfs(i, cnt + 1);
memcpy(ar, cr, sizeof(cr));
}
return;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
scanf("%d", &ar[i][j]);
br[i][j] = ar[i][j];
}
////명령5번.
for (int i = 0; i < 4; i++) {
dfs(i);
memcpy(ar, br, sizeof(br)); //초기상태.
}
printf("%d", res);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
'Problem Solving > 삼성 역량테스트' 카테고리의 다른 글
| BOJ-14500 테트로미노 (0) | 2019.11.07 |
|---|---|
| BOJ-17837 새로운 게임2 (0) | 2019.11.06 |
| BOJ-17144 미세먼지 안녕 (0) | 2019.11.06 |
| BOJ-17780 새로운 게임 (0) | 2019.11.05 |
| BOJ-17779 게리맨더링 2 (0) | 2019.11.05 |