[백준][JAVA] BOJ 12100 2048 (Easy)

 

문제 읽기🤔

---

문제

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

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

이 문제에서 다루는 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

 

 

문제 풀이📝

---

최대 5번 이동할 수 있고,

한 번 이동할 시 상,하,좌,우 4가지의 선택지가 있기 때문에 중복순열을 사용하였다.

static void game(int cnt){

        // 5번 움직인 후의 최댓값을 구한다.
        if (cnt == 5){
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++) {
                    max = Math.max(max, map[i][j]);
                }
            }
            return;
        }

        // 원본 배열을 저장할 copied 배열
        int[][] copied = new int[n][n];
        for (int i = 0; i < n; i++){
            copied[i] = Arrays.copyOf(map[i], n);
        }

        // 모든 경우의 수 탐색
        for (int dir = 0; dir < 4; dir++) {
            swipe(dir);
            game(cnt + 1);
            for (int i = 0; i < n; i++) {
                map[i] = Arrays.copyOf(copied[i], n);
            }
        }
}

또한, swipe() 메소드를 수행할 때마다 원본 배열이 수정되기 때문에

copied 배열을 만들어서 원본 배열을 복사하고 재귀함수에서 return할 때 다시 원본 배열에 덮어씌워줬다.

 

이동 명령에 따라 블럭을 이동시키거나 합치는 로직이다. (예시는 위로 이동)

// UP
for (int i = 0; i < n; i++) {
	int idx = 0;
	int number = 0;
	for (int j = 0; j < n; j++) {
        // 해당 칸이 0이 아니라면 -> 합치거나 이동시키거나 해야 함
        if (map[j][i] != 0){
            // number(직전 블록의 숫자)와 같은 수라면 -> 합친다
            if (number == map[j][i]){
                // 해당 블록을 0으로 만듦
                map[j][i] = 0;
                // 직전 블록의 숫자를 2배
                map[idx - 1][i] = number * 2;
                // 한 번 합쳐진 블록은 또 합쳐질 수 없으므로
                number = 0;
            }
            // 직전 블록의 숫자와 다른 수라면 -> 이동시킨다
            else {
                // number를 갱신한다
                number = map[j][i];
                // 기존 블록을 이동시킬 것이므로 기존 블록은 0
                map[j][i] = 0;
                // 목적지 블록의 숫자를 기존 블록의 숫자로 갱신
                map[idx][i] = number;
                // 목적지 블록의 뒤를 가리킴(목적지 갱신)
                idx++;
            }
		}
	}
}

직전 블록의 인덱스값 + 1 (직전블록 바로 다음 위치)과  직전 블록에 적힌 숫자를 저장하였고

직전 블록과 다음 블록의 숫자가 같다면, 직전 블록과 다음 블록을 합치고

직전 블록과 다음 블록의 숫자가 다르다면, 직전 블록 바로 다음으로 다음 블록을 위치시킨다.

 

구현🛠️

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    static int n;
    static int[][] map;
    static int max;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        game(0);

        System.out.println(max);

    }

    static void game(int cnt){

        // 5번 움직인 후의 최댓값을 구한다.
        if (cnt == 5){
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++) {
                    max = Math.max(max, map[i][j]);
                }
            }
            return;
        }

        // 원본 배열을 저장할 copied 배열
        int[][] copied = new int[n][n];
        for (int i = 0; i < n; i++){
            copied[i] = Arrays.copyOf(map[i], n);
        }

        // 모든 경우의 수 탐색
        for (int dir = 0; dir < 4; dir++) {
            swipe(dir);
            game(cnt + 1);
            for (int i = 0; i < n; i++) {
                map[i] = Arrays.copyOf(copied[i], n);
            }
        }
    }

    // dir: 0 - up, 1 - down, 2 - left, 3 - right
    static void swipe(int dir){

        switch (dir){
            case 0:
                for (int i = 0; i < n; i++) {
                    int idx = 0;
                    int number = 0;
                    for (int j = 0; j < n; j++) {
                        // 해당 칸이 0이 아니라면 -> 합치거나 이동시키거나 해야 함
                        if (map[j][i] != 0){
                            // number(직전 블록의 숫자)와 같은 수라면 -> 합친다
                            if (number == map[j][i]){
                                // 해당 블록을 0으로 만듦
                                map[j][i] = 0;
                                // 직전 블록의 숫자를 2배
                                map[idx - 1][i] = number * 2;
                                // 한 번 합쳐진 블록은 또 합쳐질 수 없으므로
                                number = 0;
                            }
                            // 직전 블록의 숫자와 다른 수라면 -> 이동시킨다
                            else {
                                // number를 갱신한다
                                number = map[j][i];
                                // 기존 블록을 이동시킬 것이므로 기존 블록은 0
                                map[j][i] = 0;
                                // 목적지 블록의 숫자를 기존 블록의 숫자로 갱신
                                map[idx][i] = number;
                                // 목적지 블록의 뒤를 가리킴(목적지 갱신)
                                idx++;
                            }
                        }
                    }
                }
                break;
            case 1:
                for (int i = 0; i < n; i++) {
                    int idx = n - 1;
                    int number = 0;
                    for (int j = n - 1; j >= 0 ; j--) {
                        if (map[j][i] != 0){
                            if (number == map[j][i]){
                                map[j][i] = 0;
                                map[idx + 1][i] = number * 2;
                                number = 0;
                            }
                            else {
                                number = map[j][i];
                                map[j][i] = 0;
                                map[idx][i] = number;
                                idx--;
                            }
                        }
                    }
                }
                break;
            case 2:
                for (int i = 0; i < n; i++) {
                    int idx = 0;
                    int number = 0;
                    for (int j = 0; j < n; j++) {
                        if (map[i][j] != 0){
                            if (number == map[i][j]){
                                map[i][j] = 0;
                                map[i][idx - 1] = number * 2;
                                number = 0;
                            }
                            else {
                                number = map[i][j];
                                map[i][j] = 0;
                                map[i][idx] = number;
                                idx++;
                            }
                        }
                    }
                }
                break;
            case 3:
                for (int i = 0; i < n; i++) {
                    int idx = n - 1;
                    int number = 0;
                    for (int j = n - 1; j >= 0; j--) {
                        if (map[i][j] != 0){
                            if (number == map[i][j]){
                                map[i][j] = 0;
                                map[i][idx + 1] = number * 2;
                                number = 0;
                            }
                            else {
                                number = map[i][j];
                                map[i][j] = 0;
                                map[i][idx] = number;
                                idx--;
                            }
                        }
                    }
                }
                break;
        }
    }
}

 

실행결과✅