[알고리즘] 2048
2024. 3. 22. 00:58ㆍ알고리즘 풀이/Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Point {
int value;
boolean isStop;
public Point(int value, boolean isStop) {
this.value = value;
this.isStop = isStop;
}
public Point(Point point) {
this.value = point.value;
this.isStop = false;
}
@Override
public String toString() {
return "Point{" +
"value=" + value +
", isStop=" + isStop +
'}';
}
}
static int n;
static int[][] map;
static int[][] tempMap;
static List<int[]> dirs;
static int[] tempDir;
static int[][] originalMap;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
map = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
originalMap = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
originalMap[i][j] = map[i][j];
}
}
dirs = new ArrayList<>();
tempDir = new int[5];
recursive(0);
int resultMax = Integer.MIN_VALUE;
for (int[] dir : dirs) {
copyMap();
for (int i = 0; i < 5; i++) {
move(dir[i]);
}
resultMax = Math.max(resultMax, findMaxValue());
}
System.out.println(resultMax);
// move(0);
// print();
}
private static void copyMap() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = originalMap[i][j];
}
}
}
private static int findMaxValue() {
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
maxValue = Math.max(maxValue, map[i][j]);
}
}
return maxValue;
}
private static void recursive(int depth) {
if (depth == 5) {
dirs.add(Arrays.copyOfRange(tempDir, 0, tempDir.length));
return;
}
for (int i = 0; i < 4; i++) {
tempDir[depth] = i;
recursive(depth+1);
}
}
private static void move(int dir) {
// 상하좌우
Deque<Point>[] deque = new ArrayDeque[n];
for (int i = 0; i < n; i++) {
deque[i] = new ArrayDeque<>();
}
switch (dir) {
case 0: // 상
up(deque);
gravity(deque);
toMapUp(deque);
// print();
break;
case 1: // 하
down(deque);
gravity(deque);
toMapDown(deque);
// print();
break;
case 2: // 좌
left(deque);
gravity(deque);
toMapLeft(deque);
// print();
break;
case 3: // 우
right(deque);
gravity(deque);
toMapRight(deque);
// print();
break;
}
}
private static void print() {
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 void toMapLeft(Deque<Point>[] deque) {
tempMap = new int[n][n];
for (int r = 0; r < n; r++) {
int cnt = 0;
while (!deque[r].isEmpty()) {
Point point = deque[r].pollFirst();
tempMap[r][cnt++] = point.value;
}
}
map = tempMap;
}
private static void toMapRight(Deque<Point>[] deque) {
tempMap = new int[n][n];
for (int r = 0; r < n; r++) {
int cnt = n - 1;
while (!deque[r].isEmpty()) {
tempMap[r][cnt--] = deque[r].pollFirst().value;
}
}
map = tempMap;
}
private static void toMapUp(Deque<Point>[] deque) {
tempMap = new int[n][n];
for (int c = 0; c < n; c++) {
int cnt = 0;
while (!deque[c].isEmpty()) {
tempMap[cnt++][c] = deque[c].pollFirst().value;
}
}
map = tempMap;
}
private static void toMapDown(Deque<Point>[] deque) {
tempMap = new int[n][n];
for (int c = 0; c < n; c++) {
int cnt = n - 1;
while (!deque[c].isEmpty()) {
tempMap[cnt--][c] = deque[c].pollFirst().value;
}
}
map = tempMap;
}
private static void gravity(Deque<Point>[] deque) {
Deque<Point>[] temp = new ArrayDeque[n];
for (int i = 0; i < n; i++) {
temp[i] = new ArrayDeque<>();
}
for (int i = 0; i < n; i++) {
while (!deque[i].isEmpty()) {
if (temp[i].isEmpty()) {
temp[i].add(new Point(deque[i].pollFirst()));
} else {
Point point = temp[i].peekLast();
Point curPoint = deque[i].pollFirst();
if (!point.isStop) {
if (point.value == curPoint.value) {
point.value *= 2;
// System.out.println("point.value = " + point.value);
point.isStop = true;
} else {
temp[i].add(new Point(curPoint));
}
} else {
temp[i].add(new Point(curPoint));
}
}
}
deque[i] = temp[i];
}
}
private static void left(Deque<Point>[] deque) {
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (map[r][c] == 0) {
continue;
}
deque[r].add(new Point(map[r][c], false));
}
}
}
private static void right(Deque<Point>[] deque) {
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (map[r][c] == 0) {
continue;
}
deque[r].addFirst(new Point(map[r][c], false));
}
}
}
private static void up(Deque<Point>[] deque) {
for (int c = 0; c < n; c++) {
for (int r = 0; r < n; r++) {
if (map[r][c] == 0) {
continue;
}
deque[c].add(new Point(map[r][c], false));
}
}
}
private static void down(Deque<Point>[] deque) {
for (int c = 0; c < n; c++) {
for (int r = 0; r < n; r++) {
if (map[r][c] == 0) {
continue;
}
deque[c].addFirst(new Point(map[r][c], false));
}
}
}
}
나의 풀이
- 미로 게임과 유사
- 맵에 있는 정보를 Deque으로 옮기고 각각에 이미 합쳐졌는지를 나타내는 isStop을 넣었다.
- 그리고 또 하나의 Deque(사실상 Stack으로 사용)을 이용하여 같으면 2배 다르면 넣어주기를 반복한다.
- if (map[r][c] == 0)에서 break를 했는데 그렇게 되면 0 이후에 나오는 1 이상의 값이 무시되기 때문에 continue로 해주어야 한다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] 코드트리 오카마세 (0) | 2024.03.25 |
---|---|
[알고리즘] 루돌프의 반란 (0) | 2024.03.24 |
[알고리즘] 미로 타워 디펜스 (0) | 2024.03.21 |
[알고리즘] 바이러스 검사 (0) | 2024.03.20 |
[알고리즘] 새로운 게임 2 (0) | 2024.03.19 |