[백준] 12100 2048 (Easy)

 

매일 풀어야지 풀어야지 하다가 안풀고있던 문제다

완전탐색으로 풀 수 있는데 이런 복잡한 구현문제는 확실하게 해야한다

계속 대충대충 생각하고 채점디버깅을 이용하니 반례가 넘처난다..!

 

최대 4방향 5번이므로 4^5 각각 이동시키는데 최대 20^2 정도 되니까 다 찾아봐도 된다!

 

이동시키는 move 함수 빼고는 평범하게 모든 경우를 고르는 코드다

 

move 함수에서는 방향에 따라 x,y좌표를 잡고 앞에있는 숫자부터 숫자를 옮기고

숫자가 합쳐졌는지 check배열을 통해 확인한다

 

그래서 숫자가 가다가 check=false인 같은 수를 만나면 합치고 check=true로 바꿔주자!

 

소스코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static int n,answer;
    public static int[][] map = new int[22][22];
    public static int[] dx = {0,0,-1,1};
    public static int[] dy = {1,-1,0,0};
    
    public static boolean inner(int x,int y) {
        return (0<=x && x<n && 0<=y && y<n);
    }
    
    public static void move(int op) {
        boolean[][] check = new boolean[n+1][n+1];
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                int x,y;
                if(op==0) { x=i; y=n-1-j; }
                else if(op==1) { x=i; y=j;}
                else if(op==2) { x=j; y=i;}
                else { x=n-1-j; y=i; }
                if(check[x][y] || map[x][y]==0) continue;
                int num = map[x][y];
                map[x][y]=0;
                int nx = x+dx[op]; int ny = y+dy[op];
                while(inner(nx,ny) && map[nx][ny]==0) {
                    x=nx; y=ny; nx+=dx[op]; ny+=dy[op];
                }
                if(inner(nx,ny)&&map[nx][ny]==num&&!check[nx][ny]) {
                    map[nx][ny]*=2; check[nx][ny]=true;
                }
                else map[x][y]=num;
            }
        }
    }
    
    public static void findAnswer() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                answer = Math.max(answer, map[i][j]);
            }
        }
    }
    
    
    public static void solve(int cnt) {
        findAnswer();
        if(cnt==5) return;
        
        int[][] temp = new int[22][22];
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                temp[i][j] = map[i][j];
            }
        }
        
        for(int i=0;i<4;i++) {
            move(i);
            solve(cnt+1);
            for(int j=0;j<n;j++) {
                for(int k=0;k<n;k++) {
                    map[j][k] =temp[j][k];
                }
            }
            
        }
    }
    
    public static void main(String[] args) throws FileNotFoundException {
        //System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                map[i][j] = sc.nextInt();
            }
        }
        solve(0);
        System.out.println(answer);
    }
}