[백준] 12100번 : 2048(Easy) Gold2(골드2) - JAVA[자바]

[Gold II] 2048 (Easy) - 12100

문제 링크

성능 요약

메모리: 15272 KB, 시간: 136 ms

분류

백트래킹, 브루트포스 알고리즘, 구현, 시뮬레이션

제출 일자

2024년 1월 6일 16:02:08

문제 설명

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가지로 볼 수 있다. 

 - 브루트포스를 이용하여 나올 수 있는 최대 5번의 경우를 구하는 로직(상,하,좌,우의 경우의 수를 뜻함)

 - 경우의 수를 직접 실행하는 로직

 - 최대값을 구하는 로직

 

1. 브루트포스를 이용하여 경우의 수 구하기

	private static void solution(int depth) {
        if (depth == 5) {
        	// 1. command 순서대로 명령문을 실행한다.
            copyBoard();
            for (int i = 0; i < command.length; i++) {
                moveBlock(command[i]);
            }
            // 최대값을 구한다.
            getMaxBlock();
            return;
        }

	
	    // command의 상,하,좌,우 값을 넣어준 뒤 solution을 재귀호출하여준다.
        for (int i = 0; i < 4; i++) {
            command[depth] = i;
            solution(depth + 1);
        }
    }
    
    // 기존 게임판의 모양을 복사하기 위한 로직
    private static void copyBoard() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                board[i][j] = originBoard[i][j];
            }
        }
    }

 

2. 구한 경우의 수를 순차적으로 실행 시켜주는 로직

// 입력 받은 명령문을 찾아서 실행 시켜준다.
    private static void moveBlock(int command) {
        switch (command){
            case 0:
                upBlock();
                return;
            case 1:
                downBlock();
                return;
            case 2:
                leftBlock();
                return;
            case 3:
                rightBlock();
                return;
        }
    }

 

이 부분을 구현하는 것이 가장 어려웠다.

문제를 푸는데 가장 핵심 포인트는

1. 값이 합쳐지는가? 

2. 앞에서 합쳐지면 숫자를 방향에 붙여야한다.

 

이러한 부분을 해결하기 위해서 이전 블록을 기억하는 변수와 인덱스 위치를 기억하는 변수 두가지를 선언하였다.

 

upBlock()

private static void upBlock() {
        for (int i = 0; i < n; i++) {
            // 이전 블록의 숫자를 기억하기 위한 변수
            int block = 0;
            // 삽입 할 숫자의 위치를 기억하는 변수
            int idx = 0;
            for (int j = 0; j < n; j++) {
                // 0이 아닌 경우만 생각한다.
                if (board[j][i] != 0) {
                    // 마지막으로 옮긴 블록과 현재 블록이 같다면? -> 두배가 된다.
                    if (block == board[j][i]) {
                        // 현재 삽입 할 위치가 아닌 이전의 삽입한 숫자를 두배로 만들어준다.
                        board[idx - 1][i] = block * 2;
                        // 한번만 값을 증가시킬 수 있기 때문에 방금 삽입한 위치와 블록의 숫자를 0으로 초기화
                        block = board[j][i] = 0;
                    }
                    // 마지막으로 옮긴 블록과 현재 블록이 같지않다면?
                    else {
                        // 블록의 숫자를 기억 시켜준 뒤 현재 배열의 위치를 0으로 초기화
                        block = board[j][i];
                        board[j][i] = 0;
                        // idx 위치에 블록의 값을 넣어준 뒤 Idx 증가
                        board[idx][i] = block;
                        idx++;
                    }
                }
            }
        }
    }

 

 

3. 최대값을 구하는 로직

간단하게 배열 전체를 돌면서 result 값보다 크다면 갱신하면 된다.

// 최대값을 구하는 로직
    private static void getMaxBlock() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (result < board[i][j]) {
                    result = board[i][j];
                }
            }
        }
    }

 

 

전체 코드

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

class Main {
    static int[][] board,originBoard;
    static int[] command = new int[5];
    static int result, n;

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        originBoard = new int[n][n];
        board = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                originBoard[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        solution(0);
        System.out.println(result);
    }

    private static void solution(int depth) {
        // 깊이가 5인 경우 = 최대 다섯번의 개수를 구한 경우
        if (depth == 5) {
            // 1. command 순서대로 명령문을 실행한다.
            copyBoard();
            for (int i = 0; i < command.length; i++) {
                moveBlock(command[i]);
            }
            // 최대값을 구한다.
            getMaxBlock();
            return;
        }

        // command의 상,하,좌,우 값을 넣어준 뒤 solution을 재귀호출하여준다.
        for (int i = 0; i < 4; i++) {
            command[depth] = i;
            solution(depth + 1);
        }
    }

    // 기존 게임판의 모양을 복사하기 위한 로직
    private static void copyBoard() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                board[i][j] = originBoard[i][j];
            }
        }
    }

    // 입력 받은 명령문을 찾아서 실행 시켜준다.
    private static void moveBlock(int command) {
        switch (command){
            case 0:
                upBlock();
                return;
            case 1:
                downBlock();
                return;
            case 2:
                leftBlock();
                return;
            case 3:
                rightBlock();
                return;
        }
    }

    // 위로
    private static void upBlock() {
        for (int i = 0; i < n; i++) {
            // 이전 블록의 숫자를 기억하기 위한 변수
            int block = 0;
            // 삽입 할 숫자의 위치를 기억하는 변수
            int idx = 0;
            for (int j = 0; j < n; j++) {
                // 0이 아닌 경우만 생각한다.
                if (board[j][i] != 0) {
                    // 마지막으로 옮긴 블록과 현재 블록이 같다면? -> 두배가 된다.
                    if (block == board[j][i]) {
                        // 현재 삽입 할 위치가 아닌 이전의 삽입한 숫자를 두배로 만들어준다.
                        board[idx - 1][i] = block * 2;
                        // 한번만 값을 증가시킬 수 있기 때문에 방금 삽입한 위치와 블록의 숫자를 0으로 초기화
                        block = board[j][i] = 0;
                    }
                    // 마지막으로 옮긴 블록과 현재 블록이 같지않다면?
                    else {
                        // 블록의 숫자를 기억 시켜준 뒤 현재 배열의 위치를 0으로 초기화
                        block = board[j][i];
                        board[j][i] = 0;
                        // idx 위치에 블록의 값을 넣어준 뒤 Idx 증가
                        board[idx][i] = block;
                        idx++;
                    }
                }
            }
        }
    }

    // 아래로
    private static void downBlock() {
        for (int i = 0; i < n; i++) {
            int block = 0;
            int idx = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (board[j][i] != 0) {
                    if (block == board[j][i]) {
                        board[idx + 1][i] = block * 2;
                        block = 0;
                        board[j][i] = 0;
                    } else {
                        block = board[j][i];
                        board[j][i] = 0;
                        board[idx][i] = block;
                        idx--;
                    }
                }
            }
        }
    }

    // 왼쪽으로
    private static void leftBlock() {
        for (int i = 0; i < n; i++) {
            int block = 0;
            int idx = 0;
            for (int j = 0; j < n; j++) {
                if (board[i][j] != 0) {
                    if (block == board[i][j]) {
                        board[i][idx - 1] = block * 2;
                        board[i][j] = 0;
                        block = 0;
                    } else {
                        block = board[i][j];
                        board[i][j] = 0;
                        board[i][idx] = block;
                        idx++;
                    }
                }
            }
        }
    }

    // 오른쪽으로
    private static void rightBlock() {
        for (int i = 0; i < n; i++) {
            int block = 0;
            int idx = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (board[i][j] != 0) {
                    if (block == board[i][j]) {
                        board[i][idx + 1] = block * 2;
                        block = 0;
                        board[i][j] = 0;
                    } else {
                        block = board[i][j];
                        board[i][j] = 0;
                        board[i][idx] = block;
                        idx--;
                    }
                }
            }
        }
    }

    // 최대값을 구하는 로직
    private static void getMaxBlock() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (result < board[i][j]) {
                    result = board[i][j];
                }
            }
        }
    }
}