[Java] 백준 12100 2048(Easy) / G1
2048을 구현하여 시뮬레이션 하는 문제이다.
총 5번을 이동하여 만들 수 있는 가장 높은 수를 찾으면 된다.
문제 해결 전략
사실 엄청난 수학적 알고리즘을 요하는 문제는 아니다.
얼마나 빠른 시간 내에 정교하게 2048의 움직임을 만들어내고 dfs를 통하여 가장 높은 수를 찾는 문제이다.
하지만, 구현이 쉽냐고 하면 절대 아니다.
그래서 생각해본 구현 전략은 다음과 같다.
- 2048 메커니즘 구현
- dfs를 통한 풀이
2048 구현
2048은 다음과 같이 간단한 규칙을 갖는다
움직이고자 하는 방향에 자신과 같은 수를 갖는 타일이 있으면 두 타일이 합쳐지고, 타일은 합쳐지는 두수의 합으로 변한다.
그래서 이동하고자 하는 방향에 따라, 각 행과 열의 방향에 맞는 로직을 설정하였다.
예를 들어 위의 그림 처럼, 위 → 오른쪽 이렇게 이동한다 했을 때 가장 최근의 타일을 저장할 수 있는 변수 하나와, queue 하나를 만들었다. 그리고 가장 최근의 타일과 만나게 되는 타일의 값이 갔다면 더한 값을 queue에 넣고, 그렇지 않다면 변수에 있는 값 그대로를 queue고 변수를 초기화 했다.
이와 같은 로직으로 동서남북 방향에 대한 코드를 구현하였다. 문제를 다 푼 이후에는 모든 방향에 대한 로직을 한 함수로도 동작가능하도록 함수를 수정했다.
번외로 더욱 빠르게 계산할 수 있는 로직을 생각해봤다.
밑의 두 부가 로직을 이용하면, 5회라는 작은 depth에는 크게 효과적이지 않을 수는 있어도 시행 횟수가 커진다면 충분히 연산 횟수를 줄일 수 있다.
pruning
한 회차당 얻을 수 있는 가장 최고의 값은 2배이다. 예를 들어 2회에 최고 값이 8이였다면 3회에 얻을 수 있는 최댓값은 16이다. 이를 기반으로 현재 최댓값에 (2^남은 횟수)배를 곱했을 때 기존 최댓 값을 넘지 못한다면 이에 대해서는 연산하지 않았다.
caching
hashmap을 이용하여 현재 타일들의 배치를 string으로 변환하고, 횟수(depth)를 map에 넣었다. 기존에 방문한 적이 있는 map이고, 현재보다 저장되어 있는 depth가 작을 경우 연산하지 않고, 크거나 같은 경우에 대해서만 연산을 수행하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_12100 {
private static final Map<String, Integer> visited = new HashMap<>();
private static int maxBlockValue = 0;
public static void main(String[] args) throws IOException {
int[][] map = initialize();
simulate(0, map);
System.out.println(maxBlockValue);
}
private static void simulate(int depth, int[][] map) {
if (depth == 5) {
updateMaxValue(map);
return;
}
if (isOptimizationApplicable(depth, map)) return;
int[][] originalMap = copyMap(map);
simulate(depth + 1, moveUpOrLeft(map, true)); // 위
restoreMap(map, originalMap);
simulate(depth + 1, moveDownOrRight(map, true)); // 아래
restoreMap(map, originalMap);
simulate(depth + 1, moveDownOrRight(map, false)); // 오른쪽
restoreMap(map, originalMap);
simulate(depth + 1, moveUpOrLeft(map, false)); // 왼쪽
restoreMap(map, originalMap);
}
private static boolean isOptimizationApplicable(int depth, int[][] map) {
return isAlreadyVisited(map, depth) || !canExceedMaxValue(map, depth);
}
private static boolean isAlreadyVisited(int[][] map, int depth) {
String key = convertMapToString(map);
if (visited.containsKey(key)) {
if (visited.get(key) > depth) {
visited.put(key, depth);
return false;
}
return true;
}
return false;
}
private static boolean canExceedMaxValue(int[][] map, int depth) {
int currentMax = getMaxValue(map);
int maxPossible = currentMax * (1 << (5 - depth));
return maxPossible > maxBlockValue;
}
private static int[][] moveUpOrLeft(int[][] map, boolean isVertical) {
for (int i = 0; i < map.length; i++) {
Queue<Integer> queue = new LinkedList<>();
extractAndMergeBlocks(map, isVertical, i, queue, true);
fillBlocks(map, isVertical, i, queue, true);
}
return map;
}
private static int[][] moveDownOrRight(int[][] map, boolean isVertical) {
for (int i = 0; i < map.length; i++) {
Queue<Integer> queue = new LinkedList<>();
extractAndMergeBlocks(map, isVertical, i, queue, false);
fillBlocks(map, isVertical, i, queue, false);
}
return map;
}
private static void extractAndMergeBlocks(int[][] map, boolean isVertical, int index, Queue<Integer> queue, boolean isForward) {
int temp = 0;
int size = map.length;
int start = isForward ? 0 : size - 1;
int end = isForward ? size : -1;
int step = isForward ? 1 : -1;
for (int j = start; j != end; j += step) {
int value = isVertical ? map[j][index] : map[index][j];
if (value == 0) continue;
if (temp == 0) {
temp = value;
} else if (temp == value) {
queue.add(temp * 2);
temp = 0;
} else {
queue.add(temp);
temp = value;
}
}
if (temp != 0) queue.add(temp);
}
private static void fillBlocks(int[][] map, boolean isVertical, int index, Queue<Integer> queue, boolean isForward) {
int size = map.length;
int start = isForward ? 0 : size - 1;
int end = isForward ? size : -1;
int step = isForward ? 1 : -1;
for (int j = start; j != end; j += step) {
int value = queue.isEmpty() ? 0 : queue.poll();
if (isVertical) {
map[j][index] = value;
} else {
map[index][j] = value;
}
}
}
private static int getMaxValue(int[][] map) {
int maxValue = 0;
for (int[] row : map) {
for (int value : row) {
maxValue = Math.max(maxValue, value);
}
}
return maxValue;
}
private static void updateMaxValue(int[][] map) {
maxBlockValue = Math.max(maxBlockValue, getMaxValue(map));
}
private static int[][] copyMap(int[][] map) {
int size = map.length;
int[][] newMap = new int[size][size];
for (int i = 0; i < size; i++) {
System.arraycopy(map[i], 0, newMap[i], 0, size);
}
return newMap;
}
private static void restoreMap(int[][] map, int[][] originalMap) {
for (int i = 0; i < map.length; i++) {
System.arraycopy(originalMap[i], 0, map[i], 0, map[i].length);
}
}
private static String convertMapToString(int[][] map) {
StringBuilder sb = new StringBuilder();
for (int[] row : map) {
for (int value : row) {
sb.append(value).append(".");
}
}
return sb.toString();
}
private static int[][] initialize() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(br.readLine());
int[][] map = new int[size][size];
for (int i = 0; i < size; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < size; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
return map;
}
}느낀점
단순 구현인 줄 알았으나, 생각보다 연산 시간을 줄이기 위해 고려할 점이 많았다.
그리고 이런 시뮬레이션 문제를 풀 때는 어떻게 하면 실수 없이 한번에 코드를 완성할지 충분히 고민하며 풀어야 한다고 생각한다. (사실 그게 어렵다)
문제 링크
https://www.acmicpc.net/problem/12100