baekjoon/Brute_Force
백준 12100번 : 2048(Easy) [자바]
Meluu_
2025. 6. 14. 09:59
🧫 문제 분석
✔️ 출처
📖 문제
보드 크기가 N이며, 매 이동마다 변화하기때문에
완전탐색 말고는 답이없는 것 같아서 완전탐색으로 풀이방향을 정했다.
문제에서 알고리즘 분류는 백트래킹 쪽이지만 나는 BFS로 풀었다.
BFS + 완전탐색
이 문제에서 어려웠던 건 단순히 어떻게 한 방향으로 보내면서 합치고, 다를땐 이동시키는가 이다.
합쳐지지않은 위치를 추적한다. notUnionIdx
notUnionIdx ~ 현재 위치 전까지를 이동 가능한 곳을 탐색한다.
이때 같은 값을 가지고 있다면 합친다. 값을 2배로 하고 현재 위치의 값은 0으로 저장한다.
그리고 notUinonIdx 를 합친 위치의 다음 위치로 갱신한다.
각 방향은 4개의 함수로 각각 작성하였다.
🔅 문제 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Map {
int[][] map;
int cnt;
public Map(int[][] map, int cnt) {
this.map = map;
this.cnt = cnt;
}
}
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int[][] map = new int[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
bfs(map);
System.out.println(max);
}
static int max = 0;
private static void bfs(int[][] map) {
Queue<Map> q = new LinkedList<>();
q.add(new Map(map, 0));
while (!q.isEmpty()) {
Map current = q.poll();
// 5번 이동했으면 결산
if (current.cnt == 5) {
for (int i = 0; i < n; i++) {
max = Math.max(max, Arrays.stream(current.map[i]).max().getAsInt());
}
continue;
}
// 위 방향
int[][] newMap = deepArrCopy(current.map);
moveUp(newMap);
q.add(new Map(newMap, current.cnt + 1));
// 아래
newMap = deepArrCopy(current.map);
moveDown(newMap);
q.add(new Map(newMap, current.cnt + 1));
// 왼쪽
newMap = deepArrCopy(current.map);
moveLeft(newMap);
q.add(new Map(newMap, current.cnt + 1));
//오른
newMap = deepArrCopy(current.map);
moveRight(newMap);
q.add(new Map(newMap, current.cnt + 1));
}
}
private static int[][] deepArrCopy(int[][] current) {
int[][] newMap = new int[n][n];
for (int j = 0; j < n; j++) {
newMap[j] = current[j].clone();
}
return newMap;
}
private static void moveUp(int[][] newMap) {
for (int c = 0; c < n; c++) {
int notUinonIdx = 0;
for (int r = 1; r < n; r++) {
// 현재 위치의 블록이 없다면 넘어감
if (newMap[r][c] == 0) continue;
// 합쳐지지않은 곳부터 ~ r까지 이동 가능한 곳 탐색
for (int j = notUinonIdx; j < r; j++) {
if (newMap[j][c] == newMap[r][c] ) {
newMap[j][c] *= 2;
newMap[r][c] = 0;
notUinonIdx = j + 1;
break;
} else if (newMap[j][c] == 0){
newMap[j][c] = newMap[r][c];
newMap[r][c] = 0;
break;
} else {
notUinonIdx = j + 1;
}
}
}
}
}
private static void moveDown(int[][] newMap) {
for (int c = 0; c < n; c++) {
int notUinonIdx = n-1;
for (int r = n-2; r >= 0; r--) {
// 현재 위치의 블록이 없다면 넘어감
if (newMap[r][c] == 0) continue;
// 합쳐지지않은 곳부터 ~ r까지 이동 가능한 곳 탐색
for (int j = notUinonIdx; j > r; j--) {
if (newMap[j][c] == newMap[r][c] ) {
newMap[j][c] *= 2;
newMap[r][c] = 0;
notUinonIdx = j - 1;
break;
} else if (newMap[j][c] == 0){
newMap[j][c] = newMap[r][c];
newMap[r][c] = 0;
break;
} else {
notUinonIdx = j - 1;
}
}
}
}
}
private static void moveLeft(int[][] newMap) {
for (int r = 0; r < n; r++) {
int notUinonIdx = 0;
for (int c = 1; c < n; c++) {
// 현재 위치의 블록이 없다면 넘어감
if (newMap[r][c] == 0) continue;
// 합쳐지지않은 곳부터 ~ r까지 이동 가능한 곳 탐색
for (int j = notUinonIdx; j < c; j++) {
if (newMap[r][j] == newMap[r][c]) {
newMap[r][j] *= 2;
newMap[r][c] = 0;
notUinonIdx = j + 1;
break;
} else if (newMap[r][j] == 0){
newMap[r][j] = newMap[r][c];
newMap[r][c] = 0;
break;
} else {
notUinonIdx = j + 1;
}
}
}
}
}
private static void moveRight(int[][] newMap) {
for (int r = 0; r < n; r++) {
int notUinonIdx = n-1;
for (int c = n-2; c >= 0; c--) {
// 현재 위치의 블록이 없다면 넘어감
if (newMap[r][c] == 0) continue;
// 합쳐지지않은 곳부터 ~ r까지 이동 가능한 곳 탐색
for (int j = notUinonIdx; j > c; j--) {
if (newMap[r][j] == newMap[r][c]) {
newMap[r][j] *= 2;
newMap[r][c] = 0;
notUinonIdx = j - 1;
break;
} else if (newMap[r][j] == 0){
newMap[r][j] = newMap[r][c];
newMap[r][c] = 0;
break;
} else {
notUinonIdx = j - 1;
}
}
}
}
}
}