백준 12100번 2048(자바) - dfs, 삼성 sw 역량 기출***

 

2048 (Easy) 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

58821

16501

9409

25.432%

문제

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번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

예제 입력 1 복사

3
2 2 2
4 4 4
8 8 8

예제 출력 1 복사

16

---

처음에는 클래스를 만들어서 현재 배열을 스택에 넣고, 꺼내면서 배열을 위, 아래, 양옆으로 이동시킨 배열을 만들어 다시 스택에 넣는 방식으로 구현했지만 왼쪽으로 옮기는 과정이 제대로 실행이 안 돼서 다른 블로그의 코드 방식으로 다시 구현했다.

 

실패한 이유

- 위, 왼쪽으로 이동하는 경우에는 (0,0) 칸부터 차례대로 돌면서 이동시켜야 하지만 아래, 오른쪽으로 이동하는 경우에는 오른쪽 하단인 (n-1, n-1) 칸부터 돌면서 이동시켜야 한다.

- 2차원 배열을 복사할 때는 clone()을 써도 복사가 제대로 안 되므로 깊은 복사를 하기 위해서는 for문을 이중으로 돌면서 직접 넣어줘야 한다.

추가 : move 에서 result[nx][ny] == 0인지부터 확인해야한다. 왜냐하면 result[nx][ny] 와 result[x][y]가 둘 다 0일 경우 합치는 과정을 진행해버리면 의도하지 않은 답이 나오기 때문이다.

 

소스 코드

import java.util.Scanner;

public class Main {
    static int n;
    static int result = 0;

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[][] location = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                location[i][j] = scanner.nextInt();
            }
        }
        dfs(0, 5, location);
        System.out.println(result);
    }

    static int[] dx = {-1, 1, 0, 0}; //ud
    static int[] dy = {0, 0, -1, 1}; //lr

    public static void dfs(int index, int limit, int[][] location) {
        if (index == limit) { //5번 모두 탐색 완료한 경우
            int tmp = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    tmp = Math.max(tmp, location[i][j]);
                }
            }

            result = Math.max(result, tmp);
            return;
        }

        for (int i = 0; i < 4; i++) {
            boolean[][] isMerged = new boolean[n][n]; //앞에서 합쳐진 숫자인지 확인
            int[][] now = new int[n][n];
            for (int p = 0; p < n; p++) {
                for (int j = 0; j < n; j++) {
                    now[p][j] = location[p][j];
                }
            }

            if (i == 0 || i == 2) { //위, 왼쪽
                for (int p = 0; p < n; p++) {
                    for (int j = 0; j < n; j++) {
                        move(now, isMerged, i, p, j);
                    }
                }
            } else if (i == 1 || i == 3) { //아래, 오른쪽
                for (int p = n - 1; p >= 0; p--) {
                    for (int j = n - 1; j >= 0; j--) {
                        move(now, isMerged, i, p, j);
                    }
                }
            }

            dfs(index + 1, limit, now);
        }

    }

    public static void move(int[][] location, boolean[][] isMerged, int i, int p, int j) {
        int ni = p;
        int nj = j;
        int moveRow = ni + dx[i];
        int moveCol = nj + dy[i];

        if (moveCol < 0 || moveRow < 0 || moveCol >= n || moveRow >= n) {
            return;
        }
        boolean end = false;
        while (!end) {
            if (location[moveRow][moveCol] == 0) {
                location[moveRow][moveCol] = location[ni][nj];
                location[ni][nj] = 0;
                ni = moveRow;
                nj = moveCol;
                moveRow = ni + dx[i];
                moveCol = nj + dy[i];
                if (moveCol < 0 || moveRow < 0 || moveCol >= n || moveRow >= n)
                    end = true;
            } else if (location[moveRow][moveCol] == location[ni][nj]) {
                if (!isMerged[moveRow][moveCol]) {
                    location[moveRow][moveCol] *= 2;
                    location[ni][nj] = 0;
                    isMerged[moveRow][moveCol] = true;
                }
                end = true;
            }
            else
                end = true;
        }

    }
}

 

 

참고

[Algorithm] 백준 12100번(BOJ 12100) 2048(easy) 문제 풀이(Java) (tistory.com)

[Algorithm] 백준 12100번(BOJ 12100) 2048(easy) 문제 풀이(Java)