Algorithm/Baekjoon
[백준 12100 : JAVA] 2048 (Easy)
팡트루야
2021. 8. 16. 21:53
문제
2048 게임은 4x4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.)
게임의 룰은 다음과 같다.
- 보드판은 상, 하, 좌, 우로 이동할 수 있다.
- 앞의 블록과 값이 같다면 두 값을 더한 하나의 블록으로 합쳐진다.
- 한 방향으로의 이동에서 각각의 블록은 한 번씩만 합쳐질 수 있다.
이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N($1 le N le 20$)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이 외의 값은 모두 블록을 나타낸다. 블록에 쓰여있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
풀이
이 문제는 크게 두 가지를 요구합니다.
- 중복 순열을 구할 수 있는가?
- 게임을 시뮬레이션할 수 있는가?
먼저, 최대 5번의 상하좌우 이동으로 얻을 수 있는 가장 큰 블록을 구해야하기 때문에 상하좌우 4개에 대해서 중복 순열로 5개를 뽑습니다.
최대 5번이기 때문에 3번만에도 최대값이 나올 수 있지만, 별도의 처리를 해줄 필요는 없습니다. 아래처럼 5개를 뽑았다 해보겠습니다.
[상 상 하 하 좌] <-- 상을 연속해서 두번하나 한번하나 결과는 동일합니다. 따라서, [상 하 좌] 총 3번 이동한 것과 같습니다. 따라서, 5개의 중복 순열을 백트래킹을 이용하여 구해줍니다.
두 번째로 게임을 시뮬레이션하는 것은 반복문을 이용하여 이동하고자 하는 방향으로 계속 한 칸씩 이동시켜주게끔 구현하였습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
private static int N, result;
private static Node[][] board;
public static void main(String[] args) throws Exception {
N = Integer.parseInt(in.readLine());
board = new Node[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(in.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = new Node(Integer.parseInt(st.nextToken()), false);
}
}
// 중복 순열
multisetPermutation(0, "");
System.out.println(result);
}
private static void multisetPermutation(int depth, String str) throws CloneNotSupportedException {
if (depth == 5) {
// Node[][] tmpBoard = board.clone();
Node[][] tmpBoard = new Node[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
tmpBoard[i][j] = board[i][j].clone();
}
}
for (int i = 0; i < 5; i++) {
play(tmpBoard, str.charAt(i));
initCombineCnt(tmpBoard);
}
result = Math.max(result, findMaxBlock(tmpBoard));
return;
}
for (int i = 0; i < 4; i++) {
multisetPermutation(depth + 1, str + i);
}
}
private static int findMaxBlock(Node[][] board) {
int maxVal = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
maxVal = Math.max(maxVal, board[i][j].val);
}
}
return maxVal;
}
private static void initCombineCnt(Node[][] board) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j].isCombine = false;
}
}
}
private static void play(Node[][] board, char c) {
if (c == '0') { // 상
for (int x = 0; x < N; x++) {
boolean move = true;
while (move) {
move = false;
for (int y = 1; y < N; y++) {
if (board[y - 1][x].val == 0 && board[y][x].val != 0) {
board[y - 1][x].val = board[y][x].val;
board[y - 1][x].isCombine = board[y][x].isCombine;
board[y][x].init();
move = true;
} else if (board[y - 1][x].val == board[y][x].val) {
if (!board[y - 1][x].isCombine && !board[y][x].isCombine) {
board[y - 1][x].val += board[y][x].val;
board[y - 1][x].isCombine = true;
board[y][x].init();
move = true;
}
}
}
}
}
} else if (c == '1') { // 하
for (int x = 0; x < N; x++) {
boolean move = true;
while (move) {
move = false;
for (int y = N - 2; y >= 0; y--) {
if (board[y + 1][x].val == 0 && board[y][x].val != 0) {
board[y + 1][x].val = board[y][x].val;
board[y + 1][x].isCombine = board[y][x].isCombine;
board[y][x].init();
move = true;
} else if (board[y + 1][x].val == board[y][x].val) {
if (!board[y + 1][x].isCombine && !board[y][x].isCombine) {
board[y + 1][x].val *= 2;
board[y + 1][x].isCombine = true;
board[y][x].init();
move = true;
}
}
}
}
}
} else if (c == '2') { // 좌
for (int y = 0; y < N; y++) {
boolean move = true;
while (move) {
move = false;
for (int x = 1; x < N; x++) {
if (board[y][x - 1].val == 0 && board[y][x].val != 0) {
board[y][x - 1].val = board[y][x].val;
board[y][x - 1].isCombine = board[y][x].isCombine;
board[y][x].init();
move = true;
} else if (board[y][x - 1].val == board[y][x].val) {
if (!board[y][x - 1].isCombine && !board[y][x].isCombine) {
board[y][x - 1].val *= 2;
board[y][x - 1].isCombine = true;
board[y][x].init();
move = true;
}
}
}
}
}
} else if (c == '3') { // 우
for (int y = 0; y < N; y++) {
boolean move = true;
while (move) {
move = false;
for (int x = N - 2; x >= 0; x--) {
if (board[y][x + 1].val == 0 && board[y][x].val != 0) {
board[y][x + 1].val = board[y][x].val;
board[y][x + 1].isCombine = board[y][x].isCombine;
board[y][x].init();
move = true;
} else if (board[y][x + 1].val == board[y][x].val) {
if (!board[y][x + 1].isCombine && !board[y][x].isCombine) {
board[y][x + 1].val *= 2;
board[y][x + 1].isCombine = true;
board[y][x].init();
move = true;
}
}
}
}
}
}
}
private static class Node implements Cloneable {
int val;
boolean isCombine;
public Node(int val, boolean isCombine) {
this.val = val;
this.isCombine = isCombine;
}
@Override
protected Node clone() throws CloneNotSupportedException {
// return (Node) super.clone();
return new Node(this.val, false);
}
private void init() {
this.val = 0;
this.isCombine = false;
}
}
}