12100번 - 2048 (Easy)

1. 문제 정의

 

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

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

<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

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

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

 

 - 입력 -

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

 - 출력 -

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

2. 문제 접근

딱 봐도 완전 탐색 문제처럼 보였다. dfs 와 bfs 중 뭘로 할까 하다가 dfs로 구현하기로 하였다. 총 5번을 움직인다고 하였으니, 5번에 대한 모든 방향의 경우의 수를 다 구해주면 될 듯 하다. 구현의 어려움을 주는 것은 방향별로 합치는 과정이었다. 위쪽으로 합치는 경우에는 제일 위의 행을 기준으로 합치고, 아래쪽으로 합치는 경우는 제일 아래의 행을 기준으로, 왼쪽으로는 제일 왼쪽 열을 기준으로, 오른쪽으로는 제일 오른쪽 열을 기준으로 합쳐나가야 한다.

따라서 위쪽 아래쪽으로 움직일 때는 i,j  를 그대로 넘겨서 움직이지만, 왼쪽, 오른쪽으로 움직일 때는 i,j -> j,i 로 회전축을 90도 회전시켜서 움직여줘야 한다.

 

 

 

3. 문제 풀이

1. 배열을 정의한다.

2. dfs 함수를 정의한다.

 

4. 코드

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

public class 이천사십팔 {
    static StringBuilder sb = new StringBuilder();
    static int N, result;
    static int[][] matrix, temp;
    static int[] direct;
    // 위쪽, 오른쪽, 아래, 왼쪽
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean[][] visit;


    static void input() {
        FastReader scan = new FastReader();
        N = scan.nextInt();
        matrix = new int[N + 1][N + 1];
        direct = new int[5];
        for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) matrix[i][j] = scan.nextInt();
    }

    static void dfs(int k) {

        if (k == 5) {
            //확인
            confirm();

        } else {
            for (int i = 0; i < 4; i++) {
                direct[k] = i;
                dfs(k + 1);
            }
        }

    }

    static void confirm() {
        temp = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            temp[i] = matrix[i].clone();
        }
//        direct = new int[]{1,1,0,0,0};

        for (int d = 0; d < direct.length; d++) {
            visit = new boolean[N + 1][N + 1];

            //위
            if (direct[d] == 0) {
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= N; j++) {
                        move(i, j, direct[d]);
                    }
                }
            }
            //아래
            else if (direct[d] == 2) {
                for (int i = N; i >= 1; i--) {
                    for (int j = 1; j <= N; j++) {
                        move(i, j, direct[d]);
                    }
                }
            }
            // 오른쪽
            else if (direct[d] == 1) {
                for (int i = N; i >= 1; i--) {
                    for (int j = 1; j <= N; j++) {
                        //오른쪽부터 봐야함 (j,i로 보내기)
                        move(j, i, direct[d]);
                    }
                }
            }
            //왼쪽
            else {
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= N; j++) {
                        //왼쪽부터 봐야함
                        move(j, i, direct[d]);
                    }
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (temp[i][j] > result) {
                    result = temp[i][j];
                }
            }
        }

    }

    private static void move(int x, int y, int dir) {

        if (temp[x][y] == 0) {
            return;
        }

        while (true) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            // 이동하는 것이 범위를 벗어나면
            if (nx < 1 || ny < 1 || nx > N || ny > N) {
                break;
            }
            // 이미 방문했으면
            if (visit[nx][ny]) {
                break;
            }
            // 이동하기 전 값과 이동하고 난 뒤 값이 같으면
            if (temp[nx][ny] == temp[x][y]) {
                visit[nx][ny] = true;
                temp[nx][ny] *= 2;
                temp[x][y] = 0;
                break;
            }
            //같지 않고 다른 수가 있을 때 못합침
            else if (temp[nx][ny] != 0) {
                break;
            }

            temp[nx][ny] = temp[x][y];
            temp[x][y] = 0;
            x = nx;
            y = ny;

        }

    }


    public static void main(String[] args) {
        input();
        dfs(0);
        System.out.println(result);
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

5. 회고

생각할 부분도 많고, 여차하면 틀림으로 나와서 상당히 푸는데 어려운 문제인것 같다. 디버깅으로 하나하나 확인하면서 짰다. 방향 좌표계만 나오면 이렇게 어려운 걸까..