브루트포스 문제입니다.
2048게임의 규칙에 따라서 각 위치에 숫자들이 주어졌을때
5번 움직여서 만들 수 있는 가장 큰 수를 구하는 문제입니다.
각 위치에서 상, 하, 좌, 우 4방향으로 5번 움직일 수 있으므로 4^5 경우의 수를 계산해주어야 합니다.
예외처리에서 시간을 많이 사용했는데 주로 사용한 테스트 케이스로는 아래와 같습니다.
3
1 0 1
0 0 0
1 0 1
ans = 4
각 상하좌우로 한번 씩 움직일 경우 아래와 같이 나오는지 console에 찍어보면서 확인했습니다.
2 0 2 (상)
0 0 0
0 0 0
0 0 0 (하)
0 0 0
2 0 2
2 0 0 (좌)
0 0 0
2 0 0
0 0 2 (우)
0 0 0
0 0 2
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
static int n;
static int[][] map;
static int[] dy = {0, 1, 0, -1};
static int[] dx = {1, 0, -1, 0};
static int max = 5;
static int maxValue = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
map = new int[n][n];
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
map[i][j] = sc.nextInt();
}
}
for(int i=0; i<4; ++i) {
DFS(map, i, 0); // 방향, cnt
}
System.out.println(maxValue);
}
public static void DFS(int[][] map, int dir, int cnt) {
int[][] newMap = new int[n][n];
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
newMap[i][j] = map[i][j];
if(max == cnt) {
maxValue = Math.max(maxValue, newMap[i][j]);
}
}
}
if(max == cnt) {
return;
}
moveMap(newMap, dir);
for(int i=0; i<4; ++i) {
DFS(newMap, i, cnt+1);
}
}
public static void moveMap(int[][] newMap, int dir) {
int num;
int c;
int arr[] = new int[n];
switch(dir) {
case 0: // 오른쪽
for(int i=0; i<n; ++i) {
num = 0;
c = 0;
for(int j=n-1; j>=0; --j) {
if(newMap[i][j] == 0) {
continue;
}
if(num == 0) {
num = newMap[i][j];
continue;
}
if(newMap[i][j] == num) {
arr[c] = newMap[i][j] * 2;
num = 0;
++c;
} else {
arr[c] = num;
num = newMap[i][j];
++c;
}
}
arr[c] = num;
for(int j=0; j<n; ++j) {
newMap[i][n-1-j] = arr[j];
arr[j] = 0;
}
}
break;
case 1: // 아래
for(int i=0; i<n; ++i) {
num = 0;
c = 0;
for(int j=n-1; j>=0; --j) {
if(newMap[j][i] == 0) {
continue;
}
if(num == 0) {
num = newMap[j][i];
continue;
}
if(newMap[j][i] == num) {
arr[c] = newMap[j][i] * 2;
num = 0;
++c;
} else {
arr[c] = num;
num = newMap[j][i];
++c;
}
}
arr[c] = num;
for(int j=0; j<n; ++j) {
newMap[n-1-j][i] = arr[j];
arr[j] = 0;
}
}
break;
case 2: // 왼쪽
for(int i=0; i<n; ++i) {
num = 0;
c = 0;
for(int j=0; j<n; ++j) {
if(newMap[i][j] == 0) {
continue;
}
if(num == 0) {
num = newMap[i][j];
continue;
}
if(newMap[i][j] == num) {
arr[c] = newMap[i][j] * 2;
num = 0;
++c;
} else {
arr[c] = num;
num = newMap[i][j];
++c;
}
}
arr[c] = num;
for(int j=0; j<n; ++j) {
newMap[i][j] = arr[j];
arr[j] = 0;
}
}
break;
case 3: // 위
for(int i=0; i<n; ++i) {
num = 0;
c = 0;
for(int j=0; j<n; ++j) {
if(newMap[j][i] == 0) {
continue;
}
if(num == 0) {
num = newMap[j][i];
continue;
}
if(newMap[j][i] == num) {
arr[c] = newMap[j][i] * 2;
num = 0;
++c;
} else {
arr[c] = num;
num = newMap[j][i];
++c;
}
}
arr[c] = num;
for(int j=0; j<n; ++j) {
newMap[j][i] = arr[j];
arr[j] = 0;
}
}
break;
}
}
}
'알고리즘' 카테고리의 다른 글
[Java] 백준 14499번 주사위 굴리기 (0) | 2023.02.01 |
---|---|
[Java] 백준 14890번 경사로 (0) | 2023.01.30 |
[Java] 백준 3190번 뱀 (0) | 2023.01.29 |
[Java] 백준 14502번 연구소 (0) | 2023.01.26 |
[Java] 백준 14501번 퇴사 (0) | 2023.01.25 |