[백준 2048 java 자바]2048 - DFS,구현
[Gold II] 2048 (Easy) - 12100
성능 요약
메모리: 20500 KB, 시간: 188 ms
분류
백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 구현(implementation), 시뮬레이션(simulation)
문제 설명
2048 게임은 4×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×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
풀이
개인적으로 난이도가 좀 높았다고 생각했다. dfs 말고 구현부분에서.
여러 사람들의 답을 보고, 제일 이해가고 간결한 구현을 참고했다.
- 큰 틀에서 dfs는 5번 이동이므로 depth 5번의 dfs를 구현한다.
- depth 5에서의 경우마다 map 전체를 돌아가며 가장 큰 수를 구해 답을 구한다.
- map은 재활용하며 모든 경우를 따지기 위해 depth가 깊어지는 다음 단계 전에 visited를 true로 방문 표시하고 나와서 false로 초기화 해주는 것 처럼, map을 움직이게 바꾸고 depth 빠져 나와서 다시 이전 상태로 초기화한다. (temp 그래프를 만들고 clone)
- 위,아래,왼,오 경우에 따라 밀어서 다음 경우를 따진다.(구현에서 제일 중요)
- 중요 사항
depth = 왼,오,아래로 밀기 depth3 처럼 몇 번 밀었는가,
map으로 변화 줄 경우, 되돌려서 재활용 하기
stream으로 split(" ")의 경우 초기화 하기for(int i = 0; i < N; i++){ stream(br.readLine().split(" ")) .mapToInt(Integer::parseInt).toArray(); }
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
class Main {
static int N;
static int[][] graph;//전체 지도
static int result = 0;//정답(최대값)
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
graph = new int[N][N];
for(int i = 0; i < N; i++){
stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt).toArray();
}
///초기화
dfs(0);
System.out.println(result);
}
static void dfs(int depth) {
if (depth == 5) {//1.depth(5가지 위아래왼오 경우로 민 상황)가 5인 경우 결과값 구하기
findMax();
return;
}
int[][] temp = new int[N][N];
for (int i = 0; i < N; i++) {//3.visited 초기화처럼 다음 경우의 수 이전에 map 옮긴 것을 미리 담아뒀다가 복구
temp[i] = graph[i].clone();
}
for (int i = 0; i < 4; i++) {
move(i);
dfs(depth + 1);
for (int j = 0; j < N; j++) {
graph[j] = temp[j].clone();
}
}
}
private static void findMax() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
result = Math.max(result, graph[i][j]);
}
}
}
static void move(int dir) {
// 0: 왼쪽, 1: 오른쪽, 2: 위쪽, 3: 아래쪽
LinkedList<Integer> q = new LinkedList<>(); //4. 경우 따지기
if (dir == 0) {
for (int i = 0; i < N; i++) {// 행 반복
//0으로 초기화, Q에 다 집어넣기 (한 숫자 당, 한 번만 동작하면 되므로)
for (int j = 0; j < N; j++) {
if (graph[i][j] != 0) {
q.add(graph[i][j]);//왼쪽으로 밀 때, 왼쪽 첫번째 숫자부터 (0,0)(0,1)(0,2) 순으로 큐에 넣는다.(왼쪽 첫 번째부터)
graph[i][j] = 0;//그리고 0으로 초기화
}
}
//Q에서 하나씩 꺼내서, 0이면 넣고, 0이 아니면, 이전 값과 비교해서 같으면 더하고, 다르면 넣기
int idx = 0; //graph에서 숫자 넣을 자리 target
while (!q.isEmpty()) {
int now = q.poll();//q에서 계속 꺼내 비교, q가 비면 종료
if (graph[i][idx] == 0) {//0으로 다 초기화 해놨기 때문에, 처음의 경우 초기화
graph[i][idx] = now;
} else if (graph[i][idx] == now) {//이전에 저장해둔 초기화 값==다음 꺼낸 수 (now) 이면, *2해서 넣기
graph[i][idx] *= 2;
idx++;
}else{//안같으면 그냥 합칠게 아닌거니까 꺼낸 지금 now숫자 그대로 넣어주기
idx++;
graph[i][idx] = now;
}
}
}
} else if (dir == 1) { //오른쪽
for (int i = 0; i < N; i++) {
for (int j = N-1; j >=0; j--) {
if (graph[i][j] != 0) {
q.add(graph[i][j]);
graph[i][j] = 0;
}
}
int idx = N - 1;
while (!q.isEmpty()) {
int cur = q.poll();
if (graph[i][idx] == 0) {
graph[i][idx] = cur;
} else if (graph[i][idx] == cur) {
graph[i][idx] *= 2;
idx--;
}else{
idx--;
graph[i][idx] = cur;
}
}
}
} else if (dir == 2) { //위쪽
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (graph[j][i] != 0) {
q.add(graph[j][i]);
graph[j][i] = 0;
}
}
int idx = 0;
while (!q.isEmpty()) {
int cur = q.poll();
if (graph[idx][i] == 0) {
graph[idx][i] = cur;
} else if (graph[idx][i] == cur) {
graph[idx][i] *= 2;
idx++;
}else{
idx++;
graph[idx][i] = cur;
}
}
}
}
else {
for (int i = 0; i < N; i++) {
for (int j = N-1; j >= 0; j--) {
if (graph[j][i] != 0) {
q.add(graph[j][i]);
graph[j][i] = 0;
}
}
int idx = N - 1;
while (!q.isEmpty()) {
int cur = q.poll();
if (graph[idx][i] == 0) {
graph[idx][i] = cur;
} else if (graph[idx][i] == cur) {
graph[idx][i] *= 2;
idx--;
}else{
idx--;
graph[idx][i] = cur;
}
}
}
}
}
}