BOJ 12100 2048 (Easy) [Java]
BOJ 12100 2048(Easy)
1. 문제 링크
https://www.acmicpc.net/problem/12100
2. 문제 해설
5번을 이동시키는데 각 이동마다 4개 방향으로 가지를 뻗쳐나갈 수 있는 백트래킹 문제이다.
문제를 읽어보면 구현해야할 기능은 크게 2가지다. 첫번째는 블록을 이동시키고 합치는 부분이고, 두번째는 백트래킹 과정을 통해 5번을 이동시키면서 모든 상황을 살펴 보는 부분이다. 두 기능을 어떻게 구현할지 생각해보자.
1. 블록을 이동시키고 합치는 기능 - move 메서드
백트래킹 과정에서 매 이동마다 4개의 방향을 선택할 수 있다. 즉, 매 이동마다 4개의 가지를 뻗는다. 그러므로 지금까지의 상황이 담긴 map 배열과, 이동시킬 방향을 인자로 받아야한다. 방향은 동, 서, 남, 북을 각각 0, 1, 2, 3으로 대응하였다.
이동시킬 방향이 오른쪽일 경우를 살펴보자.
한 행씩 오른쪽으로 이동시킬 것이다. 한 행의 일단 블록을 오른쪽으로 다 몰아 놓고, 합쳐야한다면 합치자. 여기서 블록을 오른쪽으로 다 몰아 놓는다는 건, 보드를 오른쪽으로 기울인다고 했을 때 블록의 위치를 생각하면 이해하기 쉽다.
오른쪽부터 살펴보면서 보드에 블록이 있으면 큐에 담고 그 위치를 빈 것으로 처리해준다. 빈 것으로 처리해주는 이유는 큐에 담은 블록들을 담은 순서대로 보면서 합치는 과정을 해준 후에 보드의 오른쪽부터 다시 블록을 놓아줄 것이기 때문이다.
이제 합치는 과정을 어떻게 구현할 것인지 살펴보자. 큐에 넣은 블록을 넣은 순서대로 빼내어서 보드의 오른쪽부터 놓아줄 것인데, 아래의 과정을 큐가 빌 때까지 반복할 것이다.
- 만약 놓아줄 위치의 보드가 비었다면 큐에서 빼낸 블록을 놓아준다.
- 만약 놓아줄 위치의 보드에 큐에서 빼낸 블록과 같은 값이 있다면 합쳐주고 다음 보드 칸으로 이동한다.
- 만약 놓아줄 위치의 보드에 블록이 있고, 그 값이 현재 큐에서 빼낸 블록과 같지 않다면 다음 보드 칸으로 이동 후 그 칸에 큐에서 빼낸 블록을 놓아준다.
이동시킬 방향이 왼쪽, 아래, 위인 경우도 위의 방식과 똑같이 하되 방향 같은 부분에서 조금만 코드를 손봐주면 된다.
2. 백트래킹을 이용하여 5번 이동하며 모든 경우를 살펴보는 기능 - solve 메서드
5번을 이동시키는데 각 이동마다 4개 방향으로 가지를 뻗쳐나간다. 즉, 매 방향마다 보드 상태가 달라진다. 그러므로 solve 메서드는 현재까지의 상태를 담은 map 배열과 몇 번째의 이동인지를 나타내는 cnt를 인자로 받는다.
49~55번째 줄이 핵심 코드이다. 매 방향마다 보드 상태가 달라지므로 move 하기 전의 보드 상태를 tmp 배열에 담아둔다. 그 후, move를 해준다. 그러면, 한번의 이동을 한 것이니 solve 메서드를 재귀적으로 호출해준다. 한 방향에 따른 모든 경우의 수 탐색이 끝나면, 다시 그 방향으로 이동하기 전으로 보드 상태를 복구시켜놓는다.
3. 코드 보기
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, ans;
static int[][] arr;
static Queue<Integer> q;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
ans = 0;
arr = new int[n][n];
q = new LinkedList<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
solve(arr, 0);
bw.write(Integer.toString(ans));
br.close();
bw.flush();
bw.close();
}
static void solve(int[][] map, int cnt) {
if (cnt == 5) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] > ans) {
ans = map[i][j];
}
}
}
return;
}
for (int i = 0; i < 4; i++) {
int[][] tmp = new int[n][n];
copyArr(map, tmp);
move(map, i);
solve(map, cnt + 1);
copyArr(tmp, map);
}
}
static void copyArr(int[][] from, int[][] to) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
to[i][j] = from[i][j];
}
}
}
static void move(int[][] map, int dir) {
if (dir == 0) {
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
if (map[i][j] > 0) {
q.add(map[i][j]);
map[i][j] = 0;
}
}
merge(map, 0, j, 1, 0);
}
} else if (dir == 1) {
for (int i = 0; i < n; i++) {
for (int j = n - 1; j >= 0; j--) {
if (map[i][j] > 0) {
q.add(map[i][j]);
map[i][j] = 0;
}
}
merge(map, i, n - 1, 0, -1);
}
} else if (dir == 2) {
for (int j = 0; j < n; j++) {
for (int i = n - 1; i >= 0; i--) {
if (map[i][j] > 0) {
q.add(map[i][j]);
map[i][j] = 0;
}
}
merge(map, n - 1, j, -1, 0);
}
} else { // dir == 3
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] > 0) {
q.add(map[i][j]);
map[i][j] = 0;
}
}
merge(map, i, 0, 0, 1);
}
}
}
static void merge(int[][] map, int startR, int startC, int dR, int dC) {
while (!q.isEmpty()) {
int val = q.poll();
if (map[startR][startC] == 0) {
map[startR][startC] = val;
} else if (map[startR][startC] == val) {
map[startR][startC] += val;
startR += dR;
startC += dC;
} else { // (map[startR][startC] !=0) && (map[startR][startC] != val)
startR += dR;
startC += dC;
map[startR][startC] = val;
}
}
}
}