12100 - 2048 (Easy)
본문
2048 게임은 $4 \times 4$ 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
 |  |  |
|---|---|---|
| <그림 1> | <그림 2> | <그림 3> |
<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
 |  |  |  |
|---|---|---|---|
| <그림 4> | <그림 5> | <그림 6> | <그림 7> |
<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
 |  |
|---|---|
| <그림 8> | <그림 9> |
<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
 |  |  |  |
|---|---|---|---|
| <그림 10> | <그림 11> | <그림 12> | <그림 13> |
<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.
 |  |
|---|---|
| <그림 14> | <그림 15> |
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 $N \times N$ 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 $5$번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 $N$ ($1 \leq N \leq 20$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 게임판의 초기 상태가 주어진다. $0$은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 $2$보다 크거나 같고, $1024$보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 $5$번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 512MB |
- $1 \leq N \leq 20$
풀이
알고리즘이 필요 없다. 문제에서 하라는 대로 게임을 구현하고, 가능한 모든 경우에 대한 시뮬레이션을 진행하면 된다.
게임판을 만드는 과정이나 현재 상황에서 가장 큰 값이 무엇인지 확인하는 것은 어렵지 않다. 4방향으로 움직일 수 있는 상황에서, 모든 경우를 탐색하는 것은 $4^5 = 1024$가지가 존재하므로 모든 경우를 확인하는 것도 어렵지는 않다. 모든 경우를 찾아보려 하므로 브루트포스 방법을 사용한다.
문제에서 까다로운 부분이라고 하면 당연히 “블럭을 이동시키는 명령을 어떻게 구현할 것인가?” 라고 할 수 있겠다. 이 문장만 보면 막막해지는데, 상황을 잘 생각해보면 간단하게 압축해낼 수 있다. 아래는 4가지 방향 중 하나, 오른쪽으로 이동하는 명령을 어떻게 압축할 수 있는지 설명한다.
- 블럭들은 같은 행의 블럭들에만 영향을 줄 수 있고, 다른 행에 있는 블럭들과는 영향을 주고받지 않는다
- 행의 가장 오른쪽에 존재하는 블럭부터 시작하여 왼쪽으로 이동하며 탐색한다
- 블럭 오른쪽이 비어있는 칸이라면 오른쪽으로 밀어버릴 수 있다. 이것은 오른쪽이 빈칸이 아니거나 벽을 만날 때까지 반복한다
- 만난 곳이 벽이라면 더 이상 움직일 수 없다
- 만난 곳이 블럭이라면 두 블럭을 합칠 수 있는지 판단한다
- 만난 블럭이 이미 합쳐졌던 블럭이라면 합칠 수 없다
- 만난 블럭이랑 현재 블럭의 숫자가 다르면 합칠 수 없다
- 만난 블럭이 합쳐졌던 블럭이 아니고 현재 블럭과 숫자가 같다면 합칠 수 있다
- 블럭 오른쪽이 비어있는 칸이라면 오른쪽으로 밀어버릴 수 있다. 이것은 오른쪽이 빈칸이 아니거나 벽을 만날 때까지 반복한다
이걸 구현하면 문제를 해결할 수 있다. 다른 방향에서도 같은 방법으로 구현하면 된다. 다만 비슷하게 만들고 옮기는 과정에서 방향과 배열의 index 등을 제대로 맞추었는지 헷갈리므로 잘 확인하도록 하자.
- 참고 알고리즘 : 브루트포스
코드
사용 언어 : C
최종 수정일 : 2023 / 1 / 19
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
#include <stdio.h>
#define MAX_IDX 20
#define MAX_MOVE 5
int n;
int answer;
#define max(a, b) (((a) > (b)) ? (a) : (b))
void backtrack(int map[][MAX_IDX], int cnt) {
if (cnt == MAX_MOVE) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
answer = max(answer, map[i][j]);
}
}
return;
}
int grid[MAX_IDX][MAX_IDX];
// RIGHT
{
for (int a = 0; a < n; ++a) {
for (int b = 0; b < n; ++b) {
grid[a][b] = map[a][b];
}
}
for (int a = 0; a < n; ++a) {
int blockIndex = n, mergedIndex = n;
if (grid[a][n - 1] != 0) {
--blockIndex;
}
for (int b = n - 2; b >= 0; --b) {
if (grid[a][b] > 0) {
if (blockIndex != n && (grid[a][b] == grid[a][blockIndex] && blockIndex < mergedIndex)) {
grid[a][blockIndex] <<= 1;
mergedIndex = blockIndex;
} else {
grid[a][--blockIndex] = grid[a][b];
}
if (b < blockIndex) {
grid[a][b] = 0;
}
}
}
}
backtrack(grid, cnt + 1);
}
// DOWN
{
for (int a = 0; a < n; ++a) {
for (int b = 0; b < n; ++b) {
grid[a][b] = map[a][b];
}
}
for (int a = 0; a < n; ++a) {
int blockIndex = n, mergedIndex = n;
if (grid[n - 1][a] != 0) {
--blockIndex;
}
for (int b = n - 2; b >= 0; --b) {
if (grid[b][a] > 0) {
if (blockIndex != n && (grid[b][a] == grid[blockIndex][a] && blockIndex < mergedIndex)) {
grid[blockIndex][a] <<= 1;
mergedIndex = blockIndex;
} else {
grid[--blockIndex][a] = grid[b][a];
}
if (b < blockIndex) {
grid[b][a] = 0;
}
}
}
}
backtrack(grid, cnt + 1);
}
// LEFT
{
for (int a = 0; a < n; ++a) {
for (int b = 0; b < n; ++b) {
grid[a][b] = map[a][b];
}
}
for (int a = 0; a < n; ++a) {
int blockIndex = -1, mergedIndex = -1;
if (grid[a][0] != 0) {
++blockIndex;
}
for (int b = 1; b < n; ++b) {
if (grid[a][b] > 0) {
if (blockIndex != -1 && (grid[a][b] == grid[a][blockIndex] && blockIndex > mergedIndex)) {
grid[a][blockIndex] <<= 1;
mergedIndex = blockIndex;
} else {
grid[a][++blockIndex] = grid[a][b];
}
if (b > blockIndex) {
grid[a][b] = 0;
}
}
}
}
backtrack(grid, cnt + 1);
}
// UP
{
for (int a = 0; a < n; ++a) {
for (int b = 0; b < n; ++b) {
grid[a][b] = map[a][b];
}
}
for (int a = 0; a < n; ++a) {
int blockIndex = -1, mergedIndex = -1;
if (grid[0][a] != 0) {
++blockIndex;
}
for (int b = 1; b < n; ++b) {
if (grid[b][a] > 0) {
if (blockIndex != -1 && (grid[b][a] == grid[blockIndex][a] && blockIndex > mergedIndex)) {
grid[blockIndex][a] <<= 1;
mergedIndex = blockIndex;
} else {
grid[++blockIndex][a] = grid[b][a];
}
if (b > blockIndex) {
grid[b][a] = 0;
}
}
}
}
backtrack(grid, cnt + 1);
}
return;
}
int main() {
int grid[MAX_IDX][MAX_IDX];
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &grid[i][j]);
}
}
backtrack(grid, 0);
printf("%d", answer);
return 0;
}