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

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

12100번: 2048 (Easy)

백준 12100번 2048(Easy) 문제

난이도 : G2

알고리즘 : 구현, 백트래킹

 

 

N이 최대 20인 NxN 배열에서 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램

상, 하, 좌, 우 4개의 경우로 5^4 -> 2^10 이므로 1024*20*20 이 정도 시간 복잡도 일거고 그냥 구현 문제구나 싶었다. 

그렇게 잘 푼 풀이는 아닌 것 같지만 다른 풀이들을 보면 상, 하, 좌, 우 한 번에 푼건 별로 없는 것 같아서 . . 비교해볼겸 올려본다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Easy2048 {
    // 상, 하, 좌, 우
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    // 옮기는 방향과 읽는방향은 반대
    static int[] next = {1,0,3,2};
    static int[][] board;
    static int N;
    static int Max;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Max = 0;
        board = new int[N][N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j]>Max) Max = board[i][j];
            }
        }
        dfs(-1, 0, 5);
        System.out.println(Max);
    }
    public static void dfs(int dir, int now, int max) {
        // 5회 이상 되면 return 
        if(now>max){
            return;
        }
        if(dir!=-1)round(dir);
        int[][] store = new int[N][N];
        for(int d=0; d<4; d++){
            //현재 값 저장
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    store[i][j] = board[i][j];
                }
            }
            // round
            dfs(d, now+1, max);
            //값  복귀
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    board[i][j] = store[i][j];
                }
            }
        }
    }
    public static void round(int dir){
        for(int i=0; i<N; i++){
            int first = -1;
            int fx, fy; // 갱신해줄위치 -> 현재 읽는 위치가 0이 아닐때, 합쳐지지 않을 때만 칸 이동 
            int x = -1; // 읽는 위치 
            int y = -1;
            if(dir<=1) { // 상, 하 방향일 때는 i열에 대해서 x를 옮겨가며 새로운 값으로 갱신 
                y=i;
                fy=i;
                x= dir==0? -1 : N;
                fx=x;
            }
            else { // 좌, 우 방향일 때는 i행에 대해서 y를 옮겨가며 새로운 값으로 갱신 
                x=i;
                fx=i;
                y= dir==2? -1 : N;
                fy=y;
            }
            for(int j=0; j<N; j++){
                // 읽는 위치 이동 
                x += dx[next[dir]];
                y += dy[next[dir]];
                //빈 블록은 넘김 
                if(board[x][y]==0)continue;
                
                // 현재 앞에 이미 합쳐진상태거나 블록이 없었을 경우 first=-1
                if(first == -1) {
                    // 지금 블록값으로 갱신
                    fx += dx[next[dir]];
                    fy += dy[next[dir]];
                    first = board[x][y];
                    board[fx][fy] = first;
                    if(fx!=x || fy!=y) board[x][y]=0;
                    continue;
                }
                // 합침
                else if(first==board[x][y] ){
                    first= -1;
                    board[fx][fy] = board[x][y]*2;
                    if(board[fx][fy]>Max) Max = board[fx][fy];
                    if(fx!=x || fy!=y) board[x][y]=0;
                }
                // 합치지 않고 그냥 이동만 시킴
                else {
                    fx += dx[next[dir]];
                    fy += dy[next[dir]];
                    first = board[x][y];
                    board[fx][fy] = board[x][y];
                    if(fx!=x || fy!=y) board[x][y]=0;
                }
            }
        }
    }
}

round 함수 

상, 하, 좌, 우 모두 dir라는 방향으로 이동하는 거로 한번에 묶었고

이동하는 방향의 제일 먼 방향 (?) 에서부터 칸을 채워줬다. 

 

int [] dx = { -1,1,0,0} , int [] dy = {0,0,-1,1} 상하좌우 배열을 만들고 칸을 읽는 위치와 결과를 저장하는 위치를 dx, dy배열을 이용해서 변경해주면 dir라는 방향에 대해서 한 번에 처리할 수 있다.

 

x, y는 칸을 읽는 위치-> 매번 한 칸씩 증가시키며 읽기 위한 값

fx, fy는 결과를 저장하는 위치-> 0이 아니고 겹치는 게 없거나 합쳐진 칸을 차례로 저장하기 위한 위치 값이다.

 

이때 dir이 0으로 윗방향으로 밀면 칸을 채우는 건 제일 위부터 아래로 읽어가며 새로 채워야 하니깐 dx [next [dir]] dy [next [dir]] 이런 식으로 다음 x, y를 찾아줬다. 

-> stack을 쓰거나 while로 0이 아닐 때까지 한 칸씩 당겨오는? 방식을 쓴 코드들도 있었다.. 

 

dfs 함수

백트래킹으로 dfs를 진행하기 전에 현재 상태를 저장해준 뒤에 함수가 종료되면 다시 이전 값으로 복구해준다. 그래야 다음 for문에서는 새로운 상태로 다시 백트래킹을 할 수 있다.