[BOJ 12100] 2048 (Easy) - JAVA, Gold2

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

사용한 알고리즘 : DFS, 백트래킹, 시뮬레이션(구현)

 

풀이전략

문제 풀이 핵심 키워드는 아래 2가지다.

 

1. DFS를 통해 모든 경우의 수를 중북 순열로 완전 탐색을 진행한다.

2. 상하좌우 이동 시, 변경된 상태를 나타내는 2차원 배열을

    원래 블록판 상태를 나타낸 2차원 배열의 내부 값 변경을 통해 구하면 시간 초과가 발생한다.

    따라서 별도의 배열을 생성하고, 생성한 배열에 필요한 값들만 넣어주는 연산을 하며 구해야한다.

 

1. DFS를 통한 중복 순열 완전 탐색

상하좌우 4방향으로 움직일 수 있고, 총 5번의 움직임 후 값을 구한다고 했으므로

결과적으로 총 1024가지의 경우의 수에서 필요한 값을 구해야 한다.

 

아래 그림은 5번의 움직임으로 가질 수 있는 액션의 모든 경우의 수를 그림으로 나타냈다.

이를 DFS와 백트래킹을 활용해 코드로 나타내면 아래와 같다.

static void dfs(int count, int map[][]){
    if(count==5){
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                maxVal = Math.max(maxVal,map[i][j]);
            }
        }
        return;
    }
    
    for(int i=1;i<=4;++i){
        int[][] transMap=convertMap(i,map);
        dfs(count+1,transMap);
    }
}

dfs 매개변수로 위 그림 경우의 수를 가질 수 있는 4^n에서, 깊이를 나타내는 n의 크기와

상하좌우 이동을 통해 생성된 맵을 전달한다.

 

n의 크기를 나타내는 count가 1씩 커지다가 목표한 액션이 5번 수행되는 순간,

해당 맵에서 가장 큰 수를 기존에 나왔던 수들 중 가장 큰 maxVal과 비교하여 더 큰 수를 maxVal로 변경하여 목표하는 5번 액션을 통해 구할 수 있는 가장 큰 값을 구한다. 그리고 return하여 더 이상 dfs가 더 깊은 레벨로 depth가 진행되지 않게한다.(백트래킹)

 

2. 상하좌우 이동 시 변경하는 맵 정보를 새로운 배열에 저장하여 반환

 

제출코드

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

public class Main {
    static int N;
    static int maxVal=0;

    static int[][] convertMap(int command, int[][] map){
        int t_map[][] = new int[N][N];

        int index;
        boolean flag;

        // ↑ 버튼을 누른 경우
        if(command==1){
            for(int i=0;i<N;++i){
                index=0;
                flag=false;
                for(int j=0;j<N;++j){
                    if(map[j][i]!=0){
                        if(!flag){
                            t_map[index][i]=map[j][i];
                            flag=true;
                        }
                        else{
                            if(t_map[index][i]==map[j][i]){
                                t_map[index][i]*=2;
                                flag=false;
                            }
                            else{
                                t_map[index+1][i]=map[j][i];
                            }
                            ++index;
                        }
                    }
                }
            }
        }
        // → 버튼을 누른 경우
        else if(command==2){
            for(int i=0;i<N;++i){
                index=N-1;
                flag=false;
                for(int j=N-1;j>=0;--j){
                    if(map[i][j]!=0){
                        if(!flag){
                            t_map[i][index]=map[i][j];
                            flag=true;
                        }
                        else{
                            if(t_map[i][index]==map[i][j]){
                                t_map[i][index]*=2;
                                flag=false;
                            }
                            else{
                                t_map[i][index-1]=map[i][j];
                            }
                            --index;
                        }
                    }
                }
            }
        }
        // ↓ 버튼을 누른 경우
        else if(command==3){
            for(int i=0;i<N;++i){
                index=N-1;
                flag=false;
                for(int j=N-1;j>=0;--j){
                    if(map[j][i]!=0){
                        if(!flag){
                            t_map[index][i]=map[j][i];
                            flag=true;
                        }
                        else{
                            if(t_map[index][i]==map[j][i]){
                                t_map[index][i]*=2;
                                flag=false;
                            }
                            else{
                                t_map[index-1][i]=map[j][i];
                            }
                            --index;
                        }
                    }
                }
            }
        }
        // ← 버튼을 누른 경우
        else if(command==4){
            for(int i=0;i<N;++i){
                index=0;
                flag=false;
                for(int j=0;j<N;++j){
                    if(map[i][j]!=0){
                        if(!flag){
                            t_map[i][index]=map[i][j];
                            flag=true;
                        }
                        else{
                            if(t_map[i][index]==map[i][j]){
                                t_map[i][index]*=2;
                                flag=false;
                            }
                            else{
                                t_map[i][index+1]=map[i][j];
                            }
                            ++index;
                        }
                    }
                }
            }
        }
        return t_map;
    }

    static void dfs(int count, int map[][]){

        if(count==5){
            for(int i=0;i<N;++i){
                for(int j=0;j<N;++j){
                    maxVal = Math.max(maxVal,map[i][j]);
                }
            }
            return;
        }
        for(int i=1;i<=4;++i){
            int[][] transMap=convertMap(i,map);
            dfs(count+1,transMap);
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        int map[][] = new int[N][N];

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;++j){
                int currentNum = Integer.parseInt(st.nextToken());
                map[i][j]=currentNum;
                maxVal = Math.max(maxVal,currentNum);
            }
        }

        dfs(0,map);

        bw.write(maxVal+"\n");
        bw.flush();
        bw.close();
    }
}