https://www.acmicpc.net/problem/12100
문제
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번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
[ 알고리즘 선택 과정 ]
한 턴에 진행시킬 수 있는 경우는 4가지 뿐.. 그것은 바로 상!하!좌!우!
그렇다면 BruteForce 아닌가? 최대 5번이라고까지 명시해줬으니 ...
Greedy 인가? 매 순간 최대의 경우를 선택하는 것이 미래의 선택에도 무조건 최적해인가?
그것은 보장할 수 없다.. 지금 당장은 최적 해가 아니더라도 그 모양이 나중에는 최적해가 될 수도 있기 때문이다..
결국 전형적인 BackTracking + 구현 문제 아닌가..?
라고 생각했다.
[ 문제 풀이 과정 ]
알고리즘은 BackTracking 임을 알았다. 이 문제의 킥은 어느 부분에 있을까? feat.흑백요리사
상/하/좌/우로 백트래킹하는 부분은 쉬울 것 같았다.
문제는.. 구현이겠지.
합쳐지는 규칙에 따라 최대 20x20의 박스를 전부 체크해보아야 하는 셈이다.
규칙을 정리해보자.
1. 상/하 방향으로 움직일 때는, y 좌표의 값인, 같은 열에 있는 칸들끼리 판단해야 한다.
2. 좌/우 방향으로 움직일 때는, x 좌표의 값인, 같은 행에 있는 칸들끼리 판단해야 한다.
3. 매 라운드마다, 각각의 행/열의 최댓값을 구한 다음에, 다 합쳤을 때 최댓값을 구해야 한다.
4. 한 라운드에서, 한 번 합쳐진 두 칸은 다시 다른 칸들과 합쳐질 수 없다. (visited 를 라운드 별로 사용해야 겠다.)
5. 각 행/열에서 합쳐질 칸들을 찾기 위해 순회할 때, 시작점은 각 방향의 끝 좌표에서 시작해야 한다. 왜냐하면 이동하려고 하는 쪽의 칸이 먼저 합쳐진다는 규칙이 있기 때문이다.
각 행 또는 열에서 합치는 로직을, 어떻게 구현할까?
Stack 을 이용해서, 다음 수가 같은 수가 나오면 합쳐서 poll 하고, 아니라면 그냥 poll만 하는 방식을 생각해봤다.
BackTracking 의 파라미터는 무엇이 필요할까? (메소드 단위를 어떻게 쪼갤까?)
여기서 핵심은, 무엇을 기준으로 하나의 단위를 가져갈 것이냐이다.
한 번 상/하/좌/우 를 하는 행동 자체를 단위로 가져간다면, 최대 총 4*4*4*4*4=1024 번의 재귀가 일어난다.
핵심은, 매 라운드마다 달라지는 것들이 무엇이냐에 초점을 맞춰야한다.
매번 MAP이 바뀔 것이다. 박스의 위치나 상태가 최대 모두 달라질 수 있다.
import java.io.*;
import java.util.*;
class Main {
public static int N;
public static int[][] MAP = null;
public static int MAX = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = getInt(br.readLine());
MAP = new int[N][N];
for (int i=0; i<N; i++) {
MAP[i] = Arrays.copyOf(getIntArr(br.readLine().split(" ")), N);
}
for (int direction=0; direction<4; direction++) {
backTracking(MAP, 1, direction);
}
// 0 상 -> x 좌표가 0인 부분부터 시작. (각 열(y)을 하나로 묶어서 계산) 0,0 -> N-1,0 / 0,1 -> N-1,1 / ... / 0,N-1 -> N-1,N-1
// 1 하 -> x 좌표가 N-1인 부분부터 시작. (각 열을 하나로 묶어서 계산)
// 2 좌 -> y 좌표가 0인 부분부터 시작. (각 행을 하나로 묶어서 계산)
// 3 우 -> y 좌표가 N-1인 부분부터 시작. (각 행을 하나로 묶어서 계산) 0,0 -> 0,N-1 / 1,0 -> 1,N-1 / ... / N-1,0 -> N-1,N-1
// 0 상. (y좌표) 0 > N-1 (x좌표) 0 > N-1
// 1 하. (y좌표) 0 > N-1 (x좌표) N-1 > 0
// 2 좌. (x좌표) 0 > N-1 (y좌표) 0 > N-1
// 3 우. (x좌표) 0 > N-1 (y좌표) N-1 > 0
System.out.println(MAX);
}
public static void backTracking(int[][] map, int depth, int side) {
// 최대 5번까지 플레이할 수 있다.
if (depth == 5) return;
if (side == 0) {
int[][] newMap = copyMap(map);
for (int j=0; j<N; j++) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int ii = 0;
for (int i=0; i<N; i++) {
if (map[i][j] != 0) {
if (stack.isEmpty()) stack.push(map[i][j]);
else {
int match = stack.pop();
if (map[i][j] == match) {
newMap[ii++][j] = match + map[i][j];
MAX = Math.max(MAX, match + map[i][j]);
} else {
newMap[ii++][j] = match;
newMap[ii++][j] = map[i][j];
MAX = Math.max(MAX, match);
MAX = Math.max(MAX, map[i][j]);
}
}
}
}
if(!stack.isEmpty()) {
int temp = stack.pop();
newMap[ii++][j] = temp;
MAX = Math.max(MAX, temp);
}
for (int i=ii; i<N; i++) {
newMap[i][j] = 0;
}
}
// 새 맵이 변동이 없다면 더이상 진행할 필요가 없다.
if (isSameMap(map, newMap)) return;
for (int direction=0; direction<4; direction++) {
System.out.println(side);
printMap(newMap);
backTracking(newMap, depth + 1, direction);
}
}
// 하
else if (side == 1) {
int[][] newMap = copyMap(map);
for (int j=0; j<N; j++) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int ii = N-1;
for (int i=N-1; i>=0; i--) {
if (map[i][j] != 0) {
if (stack.isEmpty()) stack.push(map[i][j]);
else {
int match = stack.pop();
if (map[i][j] == match) {
newMap[ii--][j] = match + map[i][j];
MAX = Math.max(MAX, match + map[i][j]);
} else {
newMap[ii--][j] = match;
newMap[ii--][j] = map[i][j];
MAX = Math.max(MAX, match);
MAX = Math.max(MAX, map[i][j]);
}
}
}
}
if(!stack.isEmpty()) {
int temp = stack.pop();
newMap[ii--][j] = temp;
MAX = Math.max(MAX, temp);
}
for (int i=ii; i>=0; i--) {
newMap[i][j] = 0;
}
}
// 새 맵이 변동이 없다면 더이상 진행할 필요가 없다.
if (isSameMap(map, newMap)) return;
for (int direction=0; direction<4; direction++) {
System.out.println(side);
printMap(newMap);
backTracking(newMap, depth + 1, direction);
}
}
// 좌
else if (side == 2) {
int[][] newMap = copyMap(map);
for (int i=0; i<N; i++) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int jj = 0;
for (int j=0; j<N; j++) {
if (map[i][j] != 0) {
if (stack.isEmpty()) stack.push(map[i][j]);
else {
int match = stack.pop();
if (map[i][j] == match) {
newMap[i][jj++] = match + map[i][j];
MAX = Math.max(MAX, match + map[i][j]);
} else {
newMap[i][jj++] = match;
newMap[i][jj++] = map[i][j];
MAX = Math.max(MAX, match);
MAX = Math.max(MAX, map[i][j]);
}
}
}
}
if(!stack.isEmpty()) {
int temp = stack.pop();
newMap[i][jj++] = temp;
MAX = Math.max(MAX, temp);
}
for (int j=jj; j<N; j++) {
newMap[i][j] = 0;
}
}
// 새 맵이 변동이 없다면 더이상 진행할 필요가 없다.
if (isSameMap(map, newMap)) return;
for (int direction=0; direction<4; direction++) {
System.out.println(side);
printMap(newMap);
backTracking(newMap, depth + 1, direction);
}
}
// 우
else if (side == 3) {
int[][] newMap = copyMap(map);
for (int i=0; i<N; i++) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int jj = N-1;
for (int j=N-1; j>=0; j--) {
if (map[i][j] != 0) {
if (stack.isEmpty()) stack.push(map[i][j]);
else {
int match = stack.pop();
if (map[i][j] == match) {
newMap[i][jj--] = match + map[i][j];
MAX = Math.max(MAX, match + map[i][j]);
} else {
newMap[i][jj--] = match;
newMap[i][jj--] = map[i][j];
MAX = Math.max(MAX, match);
MAX = Math.max(MAX, map[i][j]);
}
}
}
}
if(!stack.isEmpty()) {
int temp = stack.pop();
newMap[i][jj--] = temp;
MAX = Math.max(MAX, temp);
}
for (int j=jj; j>=0; j--) {
newMap[i][j] = 0;
}
}
// 새 맵이 변동이 없다면 더이상 진행할 필요가 없다.
if (isSameMap(map, newMap)) return;
for (int direction=0; direction<4; direction++) {
System.out.println(side);
printMap(newMap);
backTracking(newMap, depth + 1, direction);
}
}
}
public static boolean isSameMap(int[][] map, int[][] newMap) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (map[i][j] != newMap[i][j]) return false;
}
}
return true;
}
public static int[][] copyMap(int[][] map) {
int[][] newMap = new int[N][N];
for (int i=0; i<N; i++) {
newMap[i] = Arrays.copyOf(map[i], N);
}
return newMap;
}
public static void printMap(int[][] map) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
private static int getInt(String str) {
return Integer.parseInt(str);
}
private static int[] getIntArr(String[] strArr) {
return Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
}
}
틀린게 없는데 왜 자꾸 틀렸다고 하는지 모르겠다
[ 수정 코드 ]
맞았다. 틀렸던 이유는..
1. 계산이 안된 칸도 계산 된 것으로 처리되고 있었음
2. 5번까지 가능한건데.. 4번까지만 하고있었음.. 인덱스 설정이 제일 어려운거같다 ㅠㅠ
import java.io.*;
import java.util.*;
class Main {
public static int N;
public static int[][] MAP = null;
public static int MAX = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = getInt(br.readLine());
MAP = new int[N][N];
for (int i=0; i<N; i++) {
MAP[i] = Arrays.copyOf(getIntArr(br.readLine().split(" ")), N);
}
for (int direction=0; direction<4; direction++) {
backTracking(MAP, 1, direction);
}
// 0 상 -> x 좌표가 0인 부분부터 시작. (각 열(y)을 하나로 묶어서 계산) 0,0 -> N-1,0 / 0,1 -> N-1,1 / ... / 0,N-1 -> N-1,N-1
// 1 하 -> x 좌표가 N-1인 부분부터 시작. (각 열을 하나로 묶어서 계산)
// 2 좌 -> y 좌표가 0인 부분부터 시작. (각 행을 하나로 묶어서 계산)
// 3 우 -> y 좌표가 N-1인 부분부터 시작. (각 행을 하나로 묶어서 계산) 0,0 -> 0,N-1 / 1,0 -> 1,N-1 / ... / N-1,0 -> N-1,N-1
// 0 상. (y좌표) 0 > N-1 (x좌표) 0 > N-1
// 1 하. (y좌표) 0 > N-1 (x좌표) N-1 > 0
// 2 좌. (x좌표) 0 > N-1 (y좌표) 0 > N-1
// 3 우. (x좌표) 0 > N-1 (y좌표) N-1 > 0
System.out.println(MAX);
}
public static void backTracking(int[][] map, int depth, int side) {
// 최대 5번까지 플레이할 수 있다.
if (depth > 5) return;
if (side == 0) {
int[][] newMap = copyMap(map);
for (int j=0; j<N; j++) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int ii = 0;
for (int i=0; i<N; i++) {
if (map[i][j] != 0) {
if (stack.isEmpty()) stack.push(map[i][j]);
else {
int match = stack.pop();
if (map[i][j] == match) {
newMap[ii++][j] = match + map[i][j];
MAX = Math.max(MAX, match + map[i][j]);
} else {
newMap[ii++][j] = match;
// newMap[ii++][j] = map[i][j];
stack.push(map[i][j]);
MAX = Math.max(MAX, match);
// MAX = Math.max(MAX, map[i][j]);
}
}
}
}
if(!stack.isEmpty()) {
int temp = stack.pop();
newMap[ii++][j] = temp;
MAX = Math.max(MAX, temp);
}
for (int i=ii; i<N; i++) {
newMap[i][j] = 0;
}
}
// 새 맵이 변동이 없다면 더이상 진행할 필요가 없다.
if (isSameMap(map, newMap)) return;
for (int direction=0; direction<4; direction++) {
// System.out.println(side);
// printMap(newMap);
backTracking(newMap, depth + 1, direction);
}
}
// 하
else if (side == 1) {
int[][] newMap = copyMap(map);
for (int j=0; j<N; j++) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int ii = N-1;
for (int i=N-1; i>=0; i--) {
if (map[i][j] != 0) {
if (stack.isEmpty()) stack.push(map[i][j]);
else {
int match = stack.pop();
if (map[i][j] == match) {
newMap[ii--][j] = match + map[i][j];
MAX = Math.max(MAX, match + map[i][j]);
} else {
newMap[ii--][j] = match;
// newMap[ii--][j] = map[i][j];
stack.push(map[i][j]);
MAX = Math.max(MAX, match);
// MAX = Math.max(MAX, map[i][j]);
}
}
}
}
if(!stack.isEmpty()) {
int temp = stack.pop();
newMap[ii--][j] = temp;
MAX = Math.max(MAX, temp);
}
for (int i=ii; i>=0; i--) {
newMap[i][j] = 0;
}
}
// 새 맵이 변동이 없다면 더이상 진행할 필요가 없다.
if (isSameMap(map, newMap)) return;
for (int direction=0; direction<4; direction++) {
// System.out.println(side);
// printMap(newMap);
backTracking(newMap, depth + 1, direction);
}
}
// 좌
else if (side == 2) {
int[][] newMap = copyMap(map);
for (int i=0; i<N; i++) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int jj = 0;
for (int j=0; j<N; j++) {
if (map[i][j] != 0) {
if (stack.isEmpty()) stack.push(map[i][j]);
else {
int match = stack.pop();
if (map[i][j] == match) {
newMap[i][jj++] = match + map[i][j];
MAX = Math.max(MAX, match + map[i][j]);
} else {
newMap[i][jj++] = match;
// newMap[i][jj++] = map[i][j];
stack.push(map[i][j]);
MAX = Math.max(MAX, match);
// MAX = Math.max(MAX, map[i][j]);
}
}
}
}
if(!stack.isEmpty()) {
int temp = stack.pop();
newMap[i][jj++] = temp;
MAX = Math.max(MAX, temp);
}
for (int j=jj; j<N; j++) {
newMap[i][j] = 0;
}
}
// 새 맵이 변동이 없다면 더이상 진행할 필요가 없다.
if (isSameMap(map, newMap)) return;
for (int direction=0; direction<4; direction++) {
// System.out.println(side);
// printMap(newMap);
backTracking(newMap, depth + 1, direction);
}
}
// 우
else if (side == 3) {
int[][] newMap = copyMap(map);
for (int i=0; i<N; i++) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int jj = N-1;
for (int j=N-1; j>=0; j--) {
if (map[i][j] != 0) {
if (stack.isEmpty()) stack.push(map[i][j]);
else {
int match = stack.pop();
if (map[i][j] == match) {
newMap[i][jj--] = match + map[i][j];
MAX = Math.max(MAX, match + map[i][j]);
} else {
newMap[i][jj--] = match;
// newMap[i][jj--] = map[i][j];
stack.push(map[i][j]);
MAX = Math.max(MAX, match);
// MAX = Math.max(MAX, map[i][j]);
}
}
}
}
if(!stack.isEmpty()) {
int temp = stack.pop();
newMap[i][jj--] = temp;
MAX = Math.max(MAX, temp);
}
for (int j=jj; j>=0; j--) {
newMap[i][j] = 0;
}
}
// 새 맵이 변동이 없다면 더이상 진행할 필요가 없다.
if (isSameMap(map, newMap)) return;
for (int direction=0; direction<4; direction++) {
// System.out.println(side);
// printMap(newMap);
backTracking(newMap, depth + 1, direction);
}
}
}
public static boolean isSameMap(int[][] map, int[][] newMap) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (map[i][j] != newMap[i][j]) return false;
}
}
return true;
}
public static int[][] copyMap(int[][] map) {
int[][] newMap = new int[N][N];
for (int i=0; i<N; i++) {
newMap[i] = Arrays.copyOf(map[i], N);
}
return newMap;
}
public static void printMap(int[][] map) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
private static int getInt(String str) {
return Integer.parseInt(str);
}
private static int[] getIntArr(String[] strArr) {
return Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
}
}
감격 ㅠㅠ
'코딩테스트' 카테고리의 다른 글
| [삼성 SW역량테스트 10955] XY 문자열 1 (Java, D3) (0) | 2024.10.22 |
|---|---|
| [백준 3190] 뱀 (Java, 골드4) (2) | 2024.10.16 |
| [백준 13460] 구슬 탈출 2 (Java, 골드1) (1) | 2024.10.12 |
| [백준 17136] 색종이 붙이기 (Java, 골드2) - 후속편 (2) | 2024.10.11 |
| [백준 1715] 카드 정렬하기 (Java, 골드4) (1) | 2024.10.11 |