알고리즘/99Club
99클럽 코테 스터디 37일차 TIL + 2048 (구현, 브루트포스, 백트레킹)
dami97
2024. 8. 27. 22:20
반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제 & 키워드
- 백준 - 2048 (Easy) (문제 링크)
- 구현
- 브루트포스
- 시뮬레이션
- 백트래킹
문제 설명
2048 게임은 4x4 크기의 보드에서 혼자 즐길 수 있는 게임입니다. 게임에서의 목표는 보드 위에 있는 블록들을 상하좌우 네 방향 중 하나로 이동시켜 최대한 큰 수를 만드는 것입니다.
블록을 이동시키면 같은 값을 갖는 블록끼리 충돌하여 합쳐지며, 한 번 합쳐진 블록은 같은 이동 내에서 다시 합쳐질 수 없습니다. 예를 들어, 상단에 2, 2, 2가 있는 경우 위쪽으로 이동하면 처음 두 개의 2가 합쳐져 4가 되고, 그 다음 2와 합쳐질 수 없습니다.
이 문제에서는 보드의 크기가 N x N인 경우, 최대 5번 이동하여 만들 수 있는 가장 큰 블록의 값을 구하는 것입니다.
입력
- 첫 번째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어집니다.
- 다음 N개의 줄에는 보드의 초기 상태가 주어집니다.
- 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타냅니다.
- 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴입니다.
- 블록은 적어도 하나 주어집니다.
출력
- 최대 5번 이동하여 얻을 수 있는 가장 큰 블록의 값을 출력합니다.
입출력 예
예제 입력 1
3
2 2 2
4 4 4
8 8 8예제 출력 1
16문제 접근
- 문제 이해
- 2048 게임을 시뮬레이션하여 최대 5번 이동했을 때 얻을 수 있는 가장 큰 블록의 값을 구하는 문제입니다.
- 각 방향으로 이동시키면서 보드 상태를 갱신하고, 최적의 경로를 백트래킹으로 탐색합니다.
- 풀이 방법
- 보드의 각 상태에서 가능한 모든 방향으로 이동시켜서 최적의 상태를 찾습니다.
- 백트래킹을 통해 모든 가능한 경로를 탐색하며 최대 5번 이동한 결과를 계산합니다.
- 각 이동 후, 이동 방향에 따라 보드 상태를 복사하고 갱신하며, 재귀적으로 다음 이동을 탐색합니다.
풀이 - Java 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static final String[] commands = {"up", "down", "left", "right"};
private static int maxBlock = 0;
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
int n = Integer.parseInt(br.readLine());
Square[][] board = new Square[n][n];
for (int i = 0; i < n; i++) {
String[] line = br.readLine().split(" ");
for (int j = 0; j < line.length; j++) {
board[i][j] = new Square(Integer.parseInt(line[j]));
}
}
// 백트래킹 시작
dfs(board, 0);
// 결과 출력
System.out.println(maxBlock);
} catch (IOException e) {
e.printStackTrace();
}
}
private static void dfs(Square[][] board, int depth) {
if (depth == 5) {
// 최대값 갱신
for (Square[] row : board) {
for (Square square : row) {
maxBlock = Math.max(maxBlock, square.getValue());
}
}
return;
}
// 현재 보드 상태를 복사
Square[][] copy = new Square[board.length][board.length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
copy[i][j] = new Square(board[i][j].getValue());
}
}
// 네 방향으로 움직여보고 재귀 호출
for (String command : commands) {
move(copy, command);
dfs(copy, depth + 1);
// 재귀 호출 후 보드 상태를 원래대로 되돌림
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
copy[i][j] = new Square(board[i][j].getValue());
}
}
}
}
private static void move(Square[][] board, String command) {
switch (command) {
case "up":
for (int j = 0; j < board.length; j++) {
int idx = 0;
for (int i = 1; i < board.length; i++) {
if (board[i][j].getValue() != 0) {
int temp = board[i][j].getValue();
board[i][j].setValue(0);
if (board[idx][j].getValue() == 0) {
board[idx][j].setValue(temp);
} else if (board[idx][j].getValue() == temp && !board[idx][j].isMoved()) {
board[idx][j].setValue(board[idx][j].getValue() * 2);
board[idx][j].setMoved(true);
idx++;
} else {
idx++;
board[idx][j].setValue(temp);
}
}
}
resetMoved(board);
}
break;
case "down":
for (int j = 0; j < board.length; j++) {
int idx = board.length - 1;
for (int i = board.length - 2; i >= 0; i--) {
if (board[i][j].getValue() != 0) {
int temp = board[i][j].getValue();
board[i][j].setValue(0);
if (board[idx][j].getValue() == 0) {
board[idx][j].setValue(temp);
} else if (board[idx][j].getValue() == temp && !board[idx][j].isMoved()) {
board[idx][j].setValue(board[idx][j].getValue() * 2);
board[idx][j].setMoved(true);
idx--;
} else {
idx--;
board[idx][j].setValue(temp);
}
}
}
resetMoved(board);
}
break;
case "left":
for (int i = 0; i < board.length; i++) {
int idx = 0;
for (int j = 1; j < board.length; j++) {
if (board[i][j].getValue() != 0) {
int temp = board[i][j].getValue();
board[i][j].setValue(0);
if (board[i][idx].getValue() == 0) {
board[i][idx].setValue(temp);
} else if (board[i][idx].getValue() == temp && !board[i][idx].isMoved()) {
board[i][idx].setValue(board[i][idx].getValue() * 2);
board[i][idx].setMoved(true);
idx++;
} else {
idx++;
board[i][idx].setValue(temp);
}
}
}
resetMoved(board);
}
break;
case "right":
for (int i = 0; i < board.length; i++) {
int idx = board.length - 1;
for (int j = board.length - 2; j >= 0; j--) {
if (board[i][j].getValue() != 0) {
int temp = board[i][j].getValue();
board[i][j].setValue(0);
if (board[i][idx].getValue() == 0) {
board[i][idx].setValue(temp);
} else if (board[i][idx].getValue() == temp && !board[i][idx].isMoved()) {
board[i][idx].setValue(board[i][idx].getValue() * 2);
board[i][idx].setMoved(true);
idx--;
} else {
idx--;
board[i][idx].setValue(temp);
}
}
}
resetMoved(board);
}
break;
}
}
private static void resetMoved(Square[][] board) {
for (Square[] row : board) {
for (Square square : row) {
square.setMoved(false);
}
}
}
private static class Square {
private boolean isMoved;
private int value;
public Square(int value) {
this.value = value;
this.isMoved = false;
}
public boolean isMoved() {
return isMoved;
}
public void setMoved(boolean moved) {
isMoved = moved;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
}풀이 설명
- 초기화
- 주어진 입력으로 게임판의 상태를 초기화합니다. 각 블록은 Square 클래스로 표현되며, 이 클래스는 블록의 값과 이동 상태를 추적합니다.
- 백트래킹을 이용한 경로 탐색
- dfs(Square[][] board, int depth) 메서드를 사용하여 현재 게임판 상태에서 최대 5번의 이동을 시뮬레이션합니다.
- 각 방향으로 블록을 이동한 후의 상태를 저장하고, 재귀적으로 다음 단계로 이동합니다.
- 재귀 탐색이 끝난 후, 게임판 상태를 원래대로 복원하여 다른 방향으로의 탐색을 이어갑니다.
- 블록 이동 및 병합
- move(Square[][] board, String command) 메서드는 주어진 방향으로 블록을 이동시키고, 같은 값의 블록이 충돌하면 합칩니다.
- 합쳐진 블록은 다시 합쳐질 수 없으므로, 이를 추적하기 위해 isMoved 플래그를 사용합니다.
- 최대 블록 값 갱신
- 탐색이 끝난 후, 각 단계에서 얻을 수 있는 최대 블록 값을 계산하고, 이를 전역 변수 maxBlock에 저장하여 최종 출력합니다.
마무리하며
이번 문제는 2048 게임의 규칙을 정확히 구현하면서 백트래킹을 통해 최적의 해를 찾는 문제였습니다.
각 방향으로의 이동과 블록 병합을 구현하여 주어진 조건 내에서 최대의 블록 값을 찾아낼 수 있었습니다.