오늘의 학습 키워드
DFS
문제
https://www.acmicpc.net/problem/12100
- 플랫폼: 백준
- 문제명: 2048 (Easy)
- 난이도: 골드 1
풀이
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int maxBlock = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int[][] board = new int[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, board);
System.out.println(maxBlock);
}
public static void dfs(int playCnt, int[][] boardToMove) {
if (playCnt == 5) {
// calcMax
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
maxBlock = Math.max(maxBlock, boardToMove[i][j]);
}
}
return ;
}
// 상하좌우 모두 탐색 대상
for (Direction direction : Direction.values()) {
dfs(playCnt + 1, move(boardToMove, direction));
}
}
public static int[][] move(int[][] boardToMove, Direction direction) {
int[][] movedBoard = new int[n][n];
for (int i = 0; i < n; i++) {
int merged = 0;
int mergedCnt = 0;
int fixedCnt = 0;
for (int j = 0; j < n; j++) {
int x = 0;
int y = 0;
switch (direction) {
case LEFT:
x = i;
y = j;
break;
case RIGHT:
x = i;
y = n - 1 - j;
break;
case UP:
x = j;
y = i;
break;
case DOWN:
x = n - 1 - j;
y = i;
}
if (merged == 0 && boardToMove[x][y] != 0) {
merged = boardToMove[x][y];
} else if (merged != 0 && boardToMove[x][y] != 0) {
if (merged == boardToMove[x][y]) {
switch (direction) {
case LEFT:
movedBoard[x][mergedCnt + fixedCnt] = merged * 2;
break;
case RIGHT:
movedBoard[x][n - 1 - (mergedCnt + fixedCnt)] = merged * 2;
break;
case UP:
movedBoard[mergedCnt + fixedCnt][y] = merged * 2;
break;
case DOWN:
movedBoard[n - 1 - (mergedCnt + fixedCnt)][y] = merged * 2;
}
mergedCnt++;
merged = 0;
}
else {
switch (direction) {
case LEFT:
movedBoard[x][mergedCnt + fixedCnt] = merged;
break;
case RIGHT:
movedBoard[x][n - 1 - (mergedCnt + fixedCnt)] = merged;
break;
case UP:
movedBoard[mergedCnt + fixedCnt][y] = merged;
break;
case DOWN:
movedBoard[n - 1 - (mergedCnt + fixedCnt)][y] = merged;
}
fixedCnt++;
merged = boardToMove[x][y];
}
}
}
if (merged != 0) {
switch (direction) {
case LEFT:
movedBoard[i][mergedCnt + fixedCnt] = merged;
break;
case RIGHT:
movedBoard[i][n - 1 - (mergedCnt + fixedCnt)] = merged;
break;
case UP:
movedBoard[mergedCnt + fixedCnt][i] = merged;
break;
case DOWN:
movedBoard[n - 1 - (mergedCnt + fixedCnt)][i] = merged;
}
}
}
return movedBoard;
}
public enum Direction {
LEFT, RIGHT, UP, DOWN
}
}접근
- 최대 5번의 움직임, 보드의 크기는 최대 20*20으로 DFS를 통한 완전 탐색이 가능합니다.
- DFS시에는 상하좌우로 이동하는 경우를 모두 따져야 하는데, 이동 시 고려해야 할 점은 다음과 같습니다. 이동 위치에 아직 합쳐지지 않은 블록이 존재하는가?
- 서로 같은 숫자 블록인 경우
- 블록을 합칩니다.
- 서로 다른 숫자 블록인 경우
- 블록을 합칠 수 없기에, 기존 이동 위치에 존재하던 블록은 더이상 합쳐질 수 없는 블록으로 간주합니다.
- 한 줄로 정리하면 → 이동 위치에 아직 합쳐지지 않은 블록(즉, merge 대상이 되는 블록)을 별도로 저장한 뒤, 합칠 수 있다면 합치고 아니라면 해당 블록은 더이상 합쳐질 수 없다고 처리합니다.
int merged = 0; // 이동 위치에 아직 합쳐지지 않은 블록 int mergedCnt = 0; // 합쳐진 개수 int fixedCnt = 0; // 더이상 합쳐질 수 없다고 처리된 블록 개수
- 서로 같은 숫자 블록인 경우
- 로직은 다음과 같습니다.
public static int[][] move(int[][] boardToMove, Direction direction) { int[][] movedBoard = new int[n][n]; for (int i = 0; i < n; i++) { int merged = 0; int mergedCnt = 0; int fixedCnt = 0; for (int j = 0; j < n; j++) { int x = 0; int y = 0; switch (direction) { case LEFT: x = i; y = j; break; case RIGHT: x = i; y = n - 1 - j; break; case UP: x = j; y = i; break; case DOWN: x = n - 1 - j; y = i; } if (merged == 0 && boardToMove[x][y] != 0) { merged = boardToMove[x][y]; } else if (merged != 0 && boardToMove[x][y] != 0) { if (merged == boardToMove[x][y]) { switch (direction) { case LEFT: movedBoard[x][mergedCnt + fixedCnt] = merged * 2; break; case RIGHT: movedBoard[x][n - 1 - (mergedCnt + fixedCnt)] = merged * 2; break; case UP: movedBoard[mergedCnt + fixedCnt][y] = merged * 2; break; case DOWN: movedBoard[n - 1 - (mergedCnt + fixedCnt)][y] = merged * 2; } mergedCnt++; merged = 0; } else { switch (direction) { case LEFT: movedBoard[x][mergedCnt + fixedCnt] = merged; break; case RIGHT: movedBoard[x][n - 1 - (mergedCnt + fixedCnt)] = merged; break; case UP: movedBoard[mergedCnt + fixedCnt][y] = merged; break; case DOWN: movedBoard[n - 1 - (mergedCnt + fixedCnt)][y] = merged; } fixedCnt++; merged = boardToMove[x][y]; } } } if (merged != 0) { switch (direction) { case LEFT: movedBoard[i][mergedCnt + fixedCnt] = merged; break; case RIGHT: movedBoard[i][n - 1 - (mergedCnt + fixedCnt)] = merged; break; case UP: movedBoard[mergedCnt + fixedCnt][i] = merged; break; case DOWN: movedBoard[n - 1 - (mergedCnt + fixedCnt)][i] = merged; } } } return movedBoard; }- 모두 동일한 흐름으로 진행되지만, 움직이는 방향에 있어서 인덱스 값을 다르게 조정해야 하므로 switch문을 통해 방향에 맞는 인덱스를 지정해주었습니다.
소요 시간
30분
