문제 링크:
문제:
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
입력:
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력:
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
문제이해:
이 문제는 게임 과정을 직접 설명하는 것 보다는 실제로 게임을 해보고 이해하는 것을 추천한다.
2048 • Play the Free Online Game 링크
2048
Join the numbers and get to the 2048 tile! Careful: this game is extremely addictive!
gabrielecirulli.github.io
게임을 하고 왔다면 이해를 했을 것이다.
즉 이 문제는 5번에 이동을 통해서 만들어 질 수 있는 최대 숫자를 구하는 것이다.
구현 방향:
이 문제는 보드를 최대 5번 이동시키는 모든 경우를 탐색해야 하므로, 브루트포스(완전 탐색) 방식을 사용한다.
이를 효율적으로 구현하기 위해 백트래킹(재귀 탐색) 기법을 함께 활용한다.
각 단계마다 상·하·좌·우 네 가지 방향으로 이동을 시도하고, 그 결과를 기반으로 다음 단계를 재귀적으로 탐색한다.
이때 한 번의 이동이 보드 상태를 직접 변경하므로, 재귀 호출 전에 현재 보드를 반드시 복사(백업) 해두어야 한다.재귀가 끝난 후에는 복사해둔 보드로 원복하여, 다른 방향 탐색 시 이전 상태가 유지되도록 한다.
이 과정을 총 5회 반복하여 가능한 모든 이동 조합을 탐색하고, 그중에서 얻을 수 있는 최대 블록 값을 갱신한다.
이를 그대로 코드로 구현하면 다음과 같다.
정답 코드:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[][] matrix;
static int maxValue=Integer.MIN_VALUE;
public static void solve(int pos, int count){
//5번 이동했다면 최대값 갱신
if(count==5) {
checkMax();
return;
}
//행렬 복사해두기
int[][] backUp= new int[N][N];
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
backUp[i][j]=matrix[i][j];
}
}
// 3) 현재 pos 방향으로 한 번 이동(상=0, 하=1, 좌=2, 우=3)
switch (pos) {
case 0: moveUp(matrix); break;
case 1: moveDown(matrix); break;
case 2: moveLeft(matrix); break;
case 3: moveRight(matrix); break;
default:
}
for(int i=0; i<4; i++){
solve(i,count+1);
}
//원복
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
matrix[i][j]= backUp[i][j];
}
}
}
// 위로 이동
public static void moveUp(int[][] matrix) {
int N = matrix.length;
for (int col = 0; col < N; col++) {
boolean[] merged = new boolean[N]; // 이번 턴에 합쳐진 위치(해당 열)
for (int row = 1; row < N; row++) {
if (matrix[row][col] == 0) continue;
// 1) 바로 위가 같으면 즉시 합치기
if (matrix[row - 1][col] == matrix[row][col] && !merged[row - 1]) {
matrix[row - 1][col] *= 2;
matrix[row][col] = 0;
merged[row - 1] = true;
continue;
}
// 2) 위가 0이면 쭉 올리기
if (matrix[row - 1][col] == 0) {
int k = row;
while (k > 0 && matrix[k - 1][col] == 0) {
matrix[k - 1][col] = matrix[k][col];
matrix[k][col] = 0;
k--;
}
// 올린 뒤 바로 위가 같으면 1회 합치기
if (k > 0 && matrix[k - 1][col] == matrix[k][col] && !merged[k - 1]) {
matrix[k - 1][col] *= 2;
matrix[k][col] = 0;
merged[k - 1] = true;
}
}
}
}
}
// 아래로 이동
public static void moveDown(int[][] matrix) {
int N = matrix.length;
for (int col = 0; col < N; col++) {
boolean[] merged = new boolean[N]; // 이번 턴에 합쳐진 위치(해당 열)
for (int row = N - 2; row >= 0; row--) {
if (matrix[row][col] == 0) continue;
// 1) 바로 아래가 같으면 즉시 합치기
if (matrix[row + 1][col] == matrix[row][col] && !merged[row + 1]) {
matrix[row + 1][col] *= 2;
matrix[row][col] = 0;
merged[row + 1] = true;
continue;
}
// 2) 아래가 0이면 쭉 내리기
if (matrix[row + 1][col] == 0) {
int k = row;
while (k + 1 < N && matrix[k + 1][col] == 0) {
matrix[k + 1][col] = matrix[k][col];
matrix[k][col] = 0;
k++;
}
// 내린 뒤 바로 아래가 같으면 1회 합치기
if (k + 1 < N && matrix[k + 1][col] == matrix[k][col] && !merged[k + 1]) {
matrix[k + 1][col] *= 2;
matrix[k][col] = 0;
merged[k + 1] = true;
}
}
}
}
}
// 좌로 이동
public static void moveLeft(int[][] matrix) {
int N = matrix.length;
for (int row = 0; row < N; row++) {
boolean[] merged = new boolean[N]; // 이번 턴에 합쳐진 위치(해당 행)
for (int col = 1; col < N; col++) {
if (matrix[row][col] == 0) continue;
// 1) 바로 왼쪽이 같으면 즉시 합치기
if (matrix[row][col - 1] == matrix[row][col] && !merged[col - 1]) {
matrix[row][col - 1] *= 2;
matrix[row][col] = 0;
merged[col - 1] = true;
continue;
}
// 2) 왼쪽이 0이면 쭉 당기기
if (matrix[row][col - 1] == 0) {
int k = col;
while (k - 1 >= 0 && matrix[row][k - 1] == 0) {
matrix[row][k - 1] = matrix[row][k];
matrix[row][k] = 0;
k--;
}
// 당긴 뒤 바로 왼쪽이 같으면 1회 합치기
if (k - 1 >= 0 && matrix[row][k - 1] == matrix[row][k] && !merged[k - 1]) {
matrix[row][k - 1] *= 2;
matrix[row][k] = 0;
merged[k - 1] = true;
}
}
}
}
}
// 우로 이동
public static void moveRight(int[][] matrix) {
int N = matrix.length;
for (int row = 0; row < N; row++) {
boolean[] merged = new boolean[N]; // 이번 턴에 합쳐진 위치(해당 행)
for (int col = N - 2; col >= 0; col--) {
if (matrix[row][col] == 0) continue;
// 1) 바로 오른쪽이 같으면 즉시 합치기
if (matrix[row][col + 1] == matrix[row][col] && !merged[col + 1]) {
matrix[row][col + 1] *= 2;
matrix[row][col] = 0;
merged[col + 1] = true;
continue;
}
// 2) 오른쪽이 0이면 쭉 밀기
if (matrix[row][col + 1] == 0) {
int k = col;
while (k + 1 < N && matrix[row][k + 1] == 0) {
matrix[row][k + 1] = matrix[row][k];
matrix[row][k] = 0;
k++;
}
// 민 뒤 바로 오른쪽이 같으면 1회 합치기
if (k + 1 < N && matrix[row][k + 1] == matrix[row][k] && !merged[k + 1]) {
matrix[row][k + 1] *= 2;
matrix[row][k] = 0;
merged[k + 1] = true;
}
}
}
}
}
//5번 시행 후 최대 값 갱신
public static void checkMax(){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
maxValue=Math.max(maxValue,matrix[i][j]);
}
}
}
public static void main(String[] args) throws IOException {
//초기 세팅
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(br.readLine());
matrix=new int[N][N];
for(int i=0; i<N; i++){
StringTokenizer st=new StringTokenizer(br.readLine());
for(int j=0; j<N; j++){
matrix[i][j]=Integer.parseInt(st.nextToken());
}
}
//초기 세팅 끝
//탐색 시작(0: 상, 1: 하, 2: 좌, 3: 우)
for(int i=0; i<4; i++){
solve(i,0);
}
System.out.println(maxValue);
}
}
마무리하며:
이번 문제는 알고리즘의 논리 자체는 단순했지만,
상·하·좌·우로 보드를 이동시키며 숫자가 합쳐지는 과정을 정확히 구현하는 것이 핵심이었다.
특히 2048 게임의 규칙처럼 “한 번 합쳐진 블록은 같은 턴에 다시 합쳐질 수 없다” 는 조건을
정확히 처리하기 위해 세밀한 인덱스 관리와 상태 복원이 필요했다.
즉, 문제의 어려움은 알고리즘적 복잡도보다도
세부 구현에서의 시뮬레이션 정확도와 보드 상태 관리(복사·원복) 에 있었다.
감사합니다.
'코딩 테스트' 카테고리의 다른 글
| [백준] 17406 배열 돌리기 4 (JAVA) (0) | 2025.11.19 |
|---|---|
| [백준] 3190 뱀 (JAVA) (0) | 2025.10.30 |
| [백준] 14889 스타트와 링크 (JAVA) (0) | 2025.10.24 |
| [백준] 17144 미세먼지 안녕! (JAVA) (0) | 2025.10.23 |
| [백준] 1700 멀티탭 스케줄링 (JAVA) (0) | 2025.10.22 |