BOJ 12100 2048 (Easy)
https://www.acmicpc.net/problem/12100
문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
_1.png) | _2.png) | _3.png) |
|---|---|---|
| <그림 1> | <그림 2> | <그림 3> |
<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
_4.png) | _5.png) | _6.png) | _7.png) |
|---|---|---|---|
| <그림 4> | <그림 5> | <그림 6> | <그림 7> |
<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
_8.png) | _9.png) |
|---|---|
| <그림 8> | <그림 9> |
<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
_10.png) | _11.png) | _12.png) | _13.png) |
|---|---|---|---|
| <그림 10> | <그림 11> | <그림 12> | <그림 13> |
<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.
_14.png) | _15.png) |
|---|---|
| <그림 14> | <그림 15> |
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
예제 입력 1
3 2 2 2 4 4 4 8 8 8
예제 출력 1
16
코드
이번 문제는 단순 시뮬레이션 문제였다.
특정 방향으로 이동시킬 때 숫자가 합쳐지는 알고리즘을 구현하기가 조금 복잡해서 구현에 시간이 조금 많이 걸렸다.
정말 너무 싫은 문제다.
아마 코드를 더 정리할 수 있는 부분이 있을 거 같지만, 단순 시뮬레이션 문제이기 때문에 정리한다고 해서 크게 얻어갈 수 있는 게 없을 것 같아 이 정도로 마무리 한다.
왼쪽, 오른쪽, 위, 아래로 움직이는 알고리즘은 거의 비슷하기 때문에 왼쪽으로 움직이는 함수 부분만 주석을 달았다.
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static final int MAX_DEPTH = 5;
static int N;
static int maxBlock = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] board = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
searchMaxBlock(board, 0);
System.out.println(maxBlock);
}
static void searchMaxBlock(int[][] board, int depth) {
if(depth == MAX_DEPTH) {
int block = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
block = Integer.max(block, board[i][j]);
}
}
maxBlock = Integer.max(maxBlock, block);
return;
}
for (int i = 0; i < 4; i++) {
int[][] newBoard = deepCopyOf(board);
switch (i) {
case 0: right(newBoard); break;
case 1: up(newBoard); break;
case 2: left(newBoard); break;
default: down(newBoard); break;
}
searchMaxBlock(newBoard, depth + 1);
}
}
static int[][] deepCopyOf(int[][] board) {
int[][] newBoard = new int[N][];
for (int j = 0; j < N; j++) {
newBoard[j] = board[j].clone();
}
return newBoard;
}
static void left(int[][] board) {
for (int i = 0; i < N; i++) {
int lastCombined = -1; // 마지막으로 숫자가 합쳐진 위치
// 왼쪽에서 첫 번째 칸을 왼쪽으로 움직이는 것은 의미가 없으므로 두 번째 칸부터 이동 여부 검사
for (int j = 1; j < N; j++) {
// 검사 대상 칸에 숫자가 있을 경우, 검사 진행
if(board[i][j] != 0) {
// 검사 대상 칸의 왼쪽에 있는 숫자 중 가장 가까운 숫자의 인덱스를 탐색
int k = j - 1;
for (; k >= 0 && board[i][k] == 0; k--) ;
// 1. 검사 대상 칸 왼쪽에 아무 숫자가 없거나
// 2. 검사 대상 칸에 있는 숫자와 가장 가까운 왼쪽에 있는 숫자가 같지 않거나
// 3. 이번 이동으로 이미 합쳐진 숫자일 경우
if(k == -1 || board[i][k] != board[i][j] || k == lastCombined) {
// 왼쪽으로 이동 (왼쪽 이동 인덱스가 기존 위치 인덱스와 동일할 경우는 제외)
if(k + 1 != j) {
board[i][k + 1] = board[i][j];
board[i][j] = 0;
}
}
// 그 외에는 합치고 마지막으로 합쳐진 위치(lastCombined)를 기억함
else {
board[i][k] <<= 1;
lastCombined = k;
board[i][j] = 0;
}
}
}
}
}
static void right(int[][] board) {
for (int i = 0; i < N; i++) {
int lastCombined = -1;
for (int j = N - 2; j >= 0; j--) {
if(board[i][j] != 0) {
int k = j + 1;
for (; k < N && board[i][k] == 0; k++) ;
if(k == N || board[i][k] != board[i][j] || k == lastCombined) {
if(k - 1 != j) {
board[i][k - 1] = board[i][j];
board[i][j] = 0;
}
} else {
board[i][k] <<= 1;
lastCombined = k;
board[i][j] = 0;
}
}
}
}
}
static void up(int[][] board) {
for (int i = 0; i < N; i++) {
int lastCombined = -1;
for (int j = 1; j < N; j++) {
if(board[j][i] != 0) {
int k = j - 1;
for (; k >= 0 && board[k][i] == 0; k--) ;
if(k == -1 || board[k][i] != board[j][i] || k == lastCombined) {
if(k + 1 != j) {
board[k + 1][i] = board[j][i];
board[j][i] = 0;
}
} else {
board[k][i] <<= 1;
lastCombined = k;
board[j][i] = 0;
}
}
}
}
}
static void down(int[][] board) {
for (int i = 0; i < N; i++) {
int lastCombined = -1;
for (int j = N - 2; j >= 0; j--) {
if(board[j][i] != 0) {
int k = j + 1;
for (; k < N && board[k][i] == 0; k++) ;
if(k == N || board[k][i] != board[j][i] || k == lastCombined) {
if(k - 1 != j) {
board[k - 1][i] = board[j][i];
board[j][i] = 0;
}
} else {
board[k][i] <<= 1;
lastCombined = k;
board[j][i] = 0;
}
}
}
}
}
}