[ 백준 12100 ] 2048 Easy ( 자바 )

[ 백준 12100 ] 2048 Easy ( java )

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

 

그림은 링크 참조

 

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

 

 

출처: 백준 코딩 테스트 연습, https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

 

 

 

 

 

 

 

핵심 

1 dfs를 이용하여 5회 이동할 방법 구하기 ( 중복순열 )

dfs를 이용하여 5회동안 상하좌우로 어디로 이동할지 정한다. 

상하좌우는 중복을 허용한다. 

 

 

 

 

 

2 블록 합치기 

이 부분에서 사람마다 방법이 다양했다. 

이동할 라인을 큐에 저정하고, 중복을 처리하여 다시 map에 넣는 방법도 있었다. 

 

 

 

나는 그냥 맵에서 이동시키는데, boolean used[y][x] 를 이용하여 이미 합쳐진 블록인지 구분하였다. 

세세한 움직이는 과정은 코드 참조 

 

 

 

 

 

 

 

 

 

 

후기 ( 이 부분은 코드를 본 후 확인 )

1 처음 제출할 때 틀려서 블록 합치기에서 틀린 줄 알았다. 하지만, dfs 기저 조건을 잘 못 적었었다... 

2 주의할 점으로 맵의 이동이 있다. 

이동한 값을 따로 저장하고 map에서 제거해야한다. 그리고 이동한 위치를 찾고 그곳에 저장! 

while로 이동할 위치를 찾기 때문에, while을 지나면 이동할 수 없거나 다른 값을 가리키는 y, x임도 주의해야한다...  

 

 

 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요! 

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
 
public class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        o_map = new int[N][N];
        map = new int[N][N];
        used = new boolean[N][N];
        
        StringTokenizer st;
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < N ; j++) {
                o_map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0);
        System.out.println(ans);
    }
    static int N; 
    static int[][] o_map, map;
    
    static int[] moveDir = new int[5];
    static boolean[][] used;
    static int ans = 2;
    static void dfs(int mi) {
        
        if(mi == 5) {
            // 오리지널 맵을 맵으로 복사 
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j < N ; j++) {
                    map[i][j] = o_map[i][j];
                }
            }
            
            // 정해진대로 이동 시작 
            int ny, nx, val;
            for(int m = 0 ; m < 5 ; m++) {
                // 매 이동마다 used[y][x] 초기화. 
                for(int i = 0 ; i < N ; i++) {
                    for(int  j = 0 ; j < N ; j++) {
                        used[i][j] = false;
                    }
                }
                int dir = moveDir[m];
                if(dir == 0) { // 위로 이동 
                    for(int x = 0 ; x < N ; x++) {
                        for(int y = 1 ; y < N ; y++) {
                            if(map[y][x] == 0)
                                continue;
                            // next y 
                            ny = y - 1;
                            // 현재 이동할 값을 val로 빼주고 map에는 0으로 표시 
                            val = map[y][x];
                            map[y][x] = 0;
                            // 범위가 밖이 되거나, 값이 0이 아닐때까지 이동 
                            while(ny>=0 && map[ny][x] == 0) {
                                ny += delta[dir][0];
                            }
                            if(ny < 0) {
                                // 범위 밖 
                                map[0][x] = val;
                            }else if(val == map[ny][x] && !used[ny][x]) {
                                // 같은 값이며 사용안됨. => 합치기 
                                used[ny][x] = true;
                                map[ny][x] = 2*val;
                            }else {
                                // 합치기 불가. 가장 위(최근)에 0으로 이동 
                                int rev = dir == 0 || dir == 2 ? 2 - dir : 4 - dir;
                                ny += delta[rev][0];
                                map[ny][x] = val;
                            }
                        }
                    }
                }else if(dir == 2) { // down 
                    for(int x = 0 ; x < N ; x++) {
                        for(int y = N-2 ; y >= 0 ; y-- ) {
                            if(map[y][x] == 0)
                                continue;
                            ny = y + 1;
                            val = map[y][x];
                            map[y][x] = 0;
                            while(ny < N && map[ny][x] == 0) {
                                ny += delta[dir][0];
                            }
                            if(ny == N) {
                                // 범위 밖 
                                map[N-1][x] = val;
                            }else if(val == map[ny][x] && !used[ny][x]) {
                                // 같은 값이며 사용안됨. => 합치기 
                                used[ny][x] = true;
                                map[ny][x] = 2*val;
                            }else {
                                // 합치기 불가. 마지막 0으로 이동 
                                int rev = dir == 0 || dir == 2 ? 2 - dir : 4 - dir;
                                ny += delta[rev][0];
                                map[ny][x] = val;
                            }
                        }
                    }
                }else if(dir == 1) { // 오른쪽 
                    for(int y = 0 ; y < N ; y++) {
                        for(int x = N - 2 ; x >= 0 ; x-- ) {
                            if(map[y][x] == 0)
                                continue;
                            nx = x + 1;
                            val = map[y][x];
                            map[y][x] = 0;
                            while(nx < N && map[y][nx] == 0) {
                                nx += delta[dir][1];
                            }
                            if(nx == N) {
                                // 범위 밖 
                                map[y][N-1] = val;
                            }else if(val == map[y][nx] && !used[y][nx]) {
                                // 같은 값이며 사용안됨. => 합치기 
                                used[y][nx] = true;
                                map[y][nx] = 2*val;
                            }else {
                                // 합치기 불가. 마지막 0으로 이동 
                                int rev = dir == 0 || dir == 2 ? 2 - dir : 4 - dir;
                                nx += delta[rev][1];
                                map[y][nx] = val;
                            }
                        }
                    }
                }else { // 왼쪽 
                    for(int y = 0 ; y < N ; y++) {
                        for(int x = 1 ; x < N ; x++ ) {
                            if(map[y][x] == 0)
                                continue;
                            nx = x - 1;
                            val = map[y][x];
                            map[y][x] = 0;
                            while(nx >= 0 && map[y][nx] == 0) {
                                nx += delta[dir][1];
                            }
                            if(nx == -1) {
                                // 범위 밖 
                                map[y][0] = val;
                            }else if(val == map[y][nx] && !used[y][nx]) {
                                // 같은 값이며 사용안됨. => 합치기 
                                used[y][nx] = true;
                                map[y][nx] = 2*val;
                            }else {
                                // 합치기 불가. 마지막 0으로 이동 
                                int rev = dir == 0 || dir == 2 ? 2 - dir : 4 - dir;
                                nx += delta[rev][1];
                                map[y][nx] = val;
                            }
                        }
                    }
                }
            }
            
            // 가장 큰 ans 값 찾기 
            for(int y = 0 ; y < N ; y++) {
                for(int x = 0 ; x < N ; x++) {
                    if(map[y][x] == 0)
                        continue;
                    if(ans < map[y][x])
                        ans = map[y][x];
                }
            }
            return;
        }
        
        // mi번째에 4방향으로 하나씩 시도해본다. 
        for(int m = 0 ; m < 4 ; m++) {
            moveDir[mi] = m;
            dfs(mi+1);
        }
    }
    static int[][] delta = {
            {-1, 0},
            {0, 1},
            {1, 0},
            {0, -1}
    };
}