[BOJ] 12100. 2048(Easy)

단순구현과 백트래킹이 합쳐진 문제이다.

이문제는 2048을 구하는 단순구현과 4가지 방향으로 5번을 가봐야하는 과정이합쳐진 문제였다. 2차원 배열을 이용하여 재귀를 도는 백트래킹은 처음 구현해봐서 어떻게 해야하는지 고민을 많이했다. dfs()란 함수에서 이차원 배열을 저장할 temp[][] 를 이용하여 해결하였다. 즉 재귀함수호출전 temp에 map을 다 저장하고 재귀함수 호출뒤 map에 temp를 다시 복원시키는 방법을 사용하였다. 간단한 방법이지만 생각하는 부분에 있어서 많은 시간을 사용하였다.

구현뿐만 아니라 전반적으로 다시 봐야할 필요가 있는 문제인 것 같다.

 

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_12100_2048Easy {
    
    static int[][] map;
    static int N;
    static int max;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        max=0;
        dfs(0);
        System.out.println(max);
    }
    
    
    static void dfs(int depth) {
        findMax();
    
        if(depth==5) {
            return;
        }
        
        
        int[][] temp=new int[N][N];
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                temp[i][j]=map[i][j];
            }
        }
        
        for(int dir=0;dir<4;dir++) {
            if(dir==0) {up();dfs(depth+1);}
            else if(dir==1) { right(); dfs(depth+1);}
            else if(dir==2) {down(); dfs(depth+1);}
            else if(dir==3) {left(); dfs(depth+1);}
            
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    map[i][j]=temp[i][j];
                }
            }
        }
        
        
    }
 
    static void findMax() {
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                max=map[i][j]>max?map[i][j]:max;
            }
        }
    }
    
    static void up() {
        for(int col=0;col<N;col++)
            moveZeroDown(col);
        
        for(int col=0;col<N;col++) {
            for(int row=0;row<=N-2;row++) {
                if(map[row][col]!=0 && checkPow2(map[row][col]+map[row+1][col])) {
                    map[row][col]=map[row][col]+map[row+1][col];
                    map[row+1][col]=0;
                    moveZeroDown(col);
                }
            }
        }
    }
    static void right() {
        for(int row=0;row<N;row++)
            moveZeroLeft(row);
        
        for(int row=0;row<N;row++) {
            for(int col=N-1;col>=1;col--) {
                if(map[row][col]!=0 && checkPow2(map[row][col]+map[row][col-1])) {
                    map[row][col]=map[row][col]+map[row][col-1];
                    map[row][col-1]=0;
                    moveZeroLeft(row);
                }
            }
        }
    }
    static void down() {
        for(int col=0;col<N;col++)
            moveZeroUp(col);
        
        for(int col=0;col<N;col++) {
            for(int row=N-1;row>=1;row--) {
                if(map[row][col]!=0 && checkPow2(map[row][col]+map[row-1][col])) {
                    map[row][col]=map[row][col]+map[row-1][col];
                    map[row-1][col]=0;
                    moveZeroUp(col);
                }
            }
        }
    }
    static void left() {
        for(int row=0;row<N;row++)
            moveZeroRight(row);
        
        for(int row=0;row<N;row++) {
            for(int col=0;col<=N-2;col++) {
                if(map[row][col]!=0 && checkPow2(map[row][col]+map[row][col+1])) {
                    map[row][col]=map[row][col]+map[row][col+1];
                    map[row][col+1]=0;
                    moveZeroRight(row);
                }
            }
        }
    }
    
    static void moveZeroLeft(int row) {
        for(int i=N-1;i>=1;i--) {
            if(map[row][i]==0) {
                for(int j=i-1;j>=0;j--) {
                    if(map[row][j]!=0) {
                        map[row][i]=map[row][j];
                        map[row][j]=0;
                        break;
                    }
                }
            }
        }
    }
    static void moveZeroRight(int row) {
        for(int i=0;i<=N-2;i++) {
            if(map[row][i]==0) {
                for(int j=i+1;j<=N-1;j++) {
                    if(map[row][j]!=0) {
                        map[row][i]=map[row][j];
                        map[row][j]=0;
                        break;
                    }
                }
            }
        }
    }
    
    static void moveZeroDown(int col) {
        for(int i=0;i<=N-2;i++) {
            if(map[i][col]==0) {
                for(int j=i+1;j<=N-1;j++) {
                    if(map[j][col]!=0) {
                        map[i][col]=map[j][col];
                        map[j][col]=0;
                        break;
                    }
                }
            }
        }
        
    }
    
    static void moveZeroUp(int col) {
        for(int i=N-1;i>=1;i--) {
            if(map[i][col]==0) {
                for(int j=i-1;j>=0;j--) {
                    if(map[j][col]!=0) {
                        map[i][col]=map[j][col];
                        map[j][col]=0;
                        break;
                    }
                }
            }
        }
    }
    
    static boolean checkPow2(int num) {
        int mod;
        while(num!=1) {
            mod=num%2;
            if(mod==0) {
                num=num/2;
            }
            else
                return false;
        }
        
        
        return true;
    }
}