[백준 12100] 2048 (Easy)(Java)

문제 링크 : https://www.acmicpc.net/problem/12100

이 문제는 백트래킹을 이용하여 문제의 조건들을 구현한다면 풀 수 있습니다.

우선 문제에 나열된 조건들을 정리해보면

1. 상하좌우 방향 중 하나로 이동하며 해당 방향으로 모든 블록이 움직인다.
2. 이동 시 같은 값을 갖는 두 블록이 충돌하면 그 값의 두 배가 되어 하나로 합쳐진다
3. 이미 합쳐진 블록은 다시 합쳐질 수 없다

이 문제의 핵심은 2,3번을 어떤 식으로 구현하는지 입니다. 결론부터 말씀드리자면 큐를 이용하여 위의 조건을 구현할 수 있습니다.

문제 접근 로직은 다음과 같습니다.

1. 움직이는 방향에 맞게 큐 안에 숫자를 넣고 해당 수를 보드판에서 0으로 초기화한다 (ex 왼쪽으로 이동할 경우 1개의 가로줄을 하나의 큐로 보고 큐 안에 왼쪽에서부터 숫자를 차례대로 넣는다)
2. 시작 인덱스를 설정하고 큐의 숫자를 가져온다 (ex 왼쪽으로 이동할 경우 0부터 시작하여 큐에서 숫자를 뽑는다)
3. 인덱스가 가리키는 현재 보드판 내의 숫자가 0이라면 큐의 숫자를 그대로 보드판에 기입한다
4. 인덱스가 가리키는 현재 보드판 내의 숫자가 큐의 숫자와 같다면 현재 보드판 내의 숫자를 2만큼 곱하고 인덱스를 1 증가한다 (이로 인해 3번 조건을 만족시킨다)
5. 그 외의 경우 인덱스를 먼저 증가시키고 큐의 숫자를 보드판에 기입한다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{

    static int N;
    static int res = 0;
    static int[][] req = new int[21][21];

    static void getMaxBlock(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(req[i][j] > res) res = req[i][j];
            }
        }
    }

    static void move(int dir){
        Queue<Integer> queue = new LinkedList<>();

        switch (dir){
            // 오른쪽
            case 0:
                for(int i=0;i<N;i++){
                    // 큐에 숫자 넣기
                    for(int j=N-1;j>=0;j--){
                        if(req[i][j]!=0) queue.add(req[i][j]);
                        req[i][j] = 0;
                    }

                    // 큐에 숫자를 하나씩 꺼내서 같은 수라면 곱해서 넣기
                    int idx = N-1;
                    while(!queue.isEmpty()){
                        int curr = queue.poll();

                        if(req[i][idx]==0) req[i][idx] = curr;
                        else if(req[i][idx]==curr){
                            req[i][idx] *= 2;
                            idx--;
                        }
                        else{
                            idx--;
                            req[i][idx]=curr;
                        }
                    }
                }
                break;

            // 아래쪽
            case 1:
                for(int i=0;i<N;i++){
                    // 큐에 숫자 넣기
                    for(int j=0;j<N;j++){
                        if(req[j][i]!=0) queue.add(req[j][i]);
                        req[j][i] = 0;
                    }

                    // 큐에 숫자를 하나씩 꺼내서 같은 수라면 곱해서 넣기
                    int idx = 0;
                    while(!queue.isEmpty()){
                        int curr = queue.poll();

                        if(req[idx][i]==0) req[idx][i] = curr;
                        else if(req[idx][i]==curr){
                            req[idx][i] *= 2;
                            idx++;
                        }
                        else{
                            idx++;
                            req[idx][i]=curr;
                        }
                    }
                }
                break;

            // 왼쪽
            case 2:
                for(int i=0;i<N;i++){
                    // 큐에 숫자 넣기
                    for(int j=0;j<N;j++){
                        if(req[i][j]!=0) queue.add(req[i][j]);
                        req[i][j] = 0;
                    }

                    // 큐에 숫자를 하나씩 꺼내서 같은 수라면 곱해서 넣기
                    int idx = 0;
                    while(!queue.isEmpty()){
                        int curr = queue.poll();

                        if(req[i][idx]==0) req[i][idx] = curr;
                        else if(req[i][idx]==curr){
                            req[i][idx] *= 2;
                            idx++;
                        }
                        else{
                            idx++;
                            req[i][idx]=curr;
                        }
                    }
                }
                break;

            // 위쪽
            case 3:
                for(int i=0;i<N;i++){
                    // 큐에 숫자 넣기
                    for(int j=N-1;j>=0;j--){
                        if(req[j][i]!=0) queue.add(req[j][i]);
                        req[j][i] = 0;
                    }

                    // 큐에 숫자를 하나씩 꺼내서 같은 수라면 곱해서 넣기
                    int idx = N-1;
                    while(!queue.isEmpty()){
                        int curr = queue.poll();

                        if(req[idx][i]==0) req[idx][i] = curr;
                        else if(req[idx][i]==curr){
                            req[idx][i] *= 2;
                            idx--;
                        }
                        else{
                            idx--;
                            req[idx][i]=curr;
                        }
                    }
                }
                break;
        }
    }

    static void backtracking(int cnt){
        if(cnt==5){
            getMaxBlock();
            return;
        }

        int[][] origin = new int[21][21];
        for(int i=0;i<N;i++){
            origin[i] = req[i].clone();
        }

        for(int i=0;i<4;i++){
            move(i);
            backtracking(cnt+1);

            for(int j=0;j<N;j++){
                req[j] = origin[j].clone();
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                req[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        backtracking(0);
        System.out.println(res);
    }
}