[ 백준 12100 ] 2048 Easy ( java )
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
그림은 링크 참조
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
출처: 백준 코딩 테스트 연습, https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
핵심
1 dfs를 이용하여 5회 이동할 방법 구하기 ( 중복순열 )
dfs를 이용하여 5회동안 상하좌우로 어디로 이동할지 정한다.
상하좌우는 중복을 허용한다.
2 블록 합치기
이 부분에서 사람마다 방법이 다양했다.
이동할 라인을 큐에 저정하고, 중복을 처리하여 다시 map에 넣는 방법도 있었다.
나는 그냥 맵에서 이동시키는데, boolean used[y][x] 를 이용하여 이미 합쳐진 블록인지 구분하였다.
세세한 움직이는 과정은 코드 참조
후기 ( 이 부분은 코드를 본 후 확인 )
1 처음 제출할 때 틀려서 블록 합치기에서 틀린 줄 알았다. 하지만, dfs 기저 조건을 잘 못 적었었다...
2 주의할 점으로 맵의 이동이 있다.
이동한 값을 따로 저장하고 map에서 제거해야한다. 그리고 이동한 위치를 찾고 그곳에 저장!
while로 이동할 위치를 찾기 때문에, while을 지나면 이동할 수 없거나 다른 값을 가리키는 y, x임도 주의해야한다...
추가적으로 더 궁금한 점 있으면 댓글 달아주세요!
코드
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
o_map = new int[N][N];
map = new int[N][N];
used = new boolean[N][N];
StringTokenizer st;
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j < N ; j++) {
o_map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0);
System.out.println(ans);
}
static int N;
static int[][] o_map, map;
static int[] moveDir = new int[5];
static boolean[][] used;
static int ans = 2;
static void dfs(int mi) {
if(mi == 5) {
// 오리지널 맵을 맵으로 복사
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < N ; j++) {
map[i][j] = o_map[i][j];
}
}
// 정해진대로 이동 시작
int ny, nx, val;
for(int m = 0 ; m < 5 ; m++) {
// 매 이동마다 used[y][x] 초기화.
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < N ; j++) {
used[i][j] = false;
}
}
int dir = moveDir[m];
if(dir == 0) { // 위로 이동
for(int x = 0 ; x < N ; x++) {
for(int y = 1 ; y < N ; y++) {
if(map[y][x] == 0)
continue;
// next y
ny = y - 1;
// 현재 이동할 값을 val로 빼주고 map에는 0으로 표시
val = map[y][x];
map[y][x] = 0;
// 범위가 밖이 되거나, 값이 0이 아닐때까지 이동
while(ny>=0 && map[ny][x] == 0) {
ny += delta[dir][0];
}
if(ny < 0) {
// 범위 밖
map[0][x] = val;
}else if(val == map[ny][x] && !used[ny][x]) {
// 같은 값이며 사용안됨. => 합치기
used[ny][x] = true;
map[ny][x] = 2*val;
}else {
// 합치기 불가. 가장 위(최근)에 0으로 이동
int rev = dir == 0 || dir == 2 ? 2 - dir : 4 - dir;
ny += delta[rev][0];
map[ny][x] = val;
}
}
}
}else if(dir == 2) { // down
for(int x = 0 ; x < N ; x++) {
for(int y = N-2 ; y >= 0 ; y-- ) {
if(map[y][x] == 0)
continue;
ny = y + 1;
val = map[y][x];
map[y][x] = 0;
while(ny < N && map[ny][x] == 0) {
ny += delta[dir][0];
}
if(ny == N) {
// 범위 밖
map[N-1][x] = val;
}else if(val == map[ny][x] && !used[ny][x]) {
// 같은 값이며 사용안됨. => 합치기
used[ny][x] = true;
map[ny][x] = 2*val;
}else {
// 합치기 불가. 마지막 0으로 이동
int rev = dir == 0 || dir == 2 ? 2 - dir : 4 - dir;
ny += delta[rev][0];
map[ny][x] = val;
}
}
}
}else if(dir == 1) { // 오른쪽
for(int y = 0 ; y < N ; y++) {
for(int x = N - 2 ; x >= 0 ; x-- ) {
if(map[y][x] == 0)
continue;
nx = x + 1;
val = map[y][x];
map[y][x] = 0;
while(nx < N && map[y][nx] == 0) {
nx += delta[dir][1];
}
if(nx == N) {
// 범위 밖
map[y][N-1] = val;
}else if(val == map[y][nx] && !used[y][nx]) {
// 같은 값이며 사용안됨. => 합치기
used[y][nx] = true;
map[y][nx] = 2*val;
}else {
// 합치기 불가. 마지막 0으로 이동
int rev = dir == 0 || dir == 2 ? 2 - dir : 4 - dir;
nx += delta[rev][1];
map[y][nx] = val;
}
}
}
}else { // 왼쪽
for(int y = 0 ; y < N ; y++) {
for(int x = 1 ; x < N ; x++ ) {
if(map[y][x] == 0)
continue;
nx = x - 1;
val = map[y][x];
map[y][x] = 0;
while(nx >= 0 && map[y][nx] == 0) {
nx += delta[dir][1];
}
if(nx == -1) {
// 범위 밖
map[y][0] = val;
}else if(val == map[y][nx] && !used[y][nx]) {
// 같은 값이며 사용안됨. => 합치기
used[y][nx] = true;
map[y][nx] = 2*val;
}else {
// 합치기 불가. 마지막 0으로 이동
int rev = dir == 0 || dir == 2 ? 2 - dir : 4 - dir;
nx += delta[rev][1];
map[y][nx] = val;
}
}
}
}
}
// 가장 큰 ans 값 찾기
for(int y = 0 ; y < N ; y++) {
for(int x = 0 ; x < N ; x++) {
if(map[y][x] == 0)
continue;
if(ans < map[y][x])
ans = map[y][x];
}
}
return;
}
// mi번째에 4방향으로 하나씩 시도해본다.
for(int m = 0 ; m < 4 ; m++) {
moveDir[mi] = m;
dfs(mi+1);
}
}
static int[][] delta = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
}
|
cs |
'CS > 알고리즘 풀이' 카테고리의 다른 글
| [ 백준 3190 ] 뱀 ( 자바 ) (0) | 2020.02.26 |
|---|---|
| [ 백준 17142 ] 연구소 3 ( 자바 ) (0) | 2020.02.22 |
| [ 백준 14502 ] 연구소 ( 자바 ) (0) | 2020.02.17 |
| [ 백준 17406 ] 배열 돌리기 4 ( 자바 ) (0) | 2020.02.17 |
| [ 백준 17136 ] 색종이 붙이기 ( 자바 ) (0) | 2020.02.17 |
