[백준_2048] (Easy).java

목차

1. 문제 해석
2. 사고 과정
3. 코드 구현
4. 회고록

---

문제 해석

문제에서 의미하는 단어들을 명확히 하는 단계입니다

2048 게임은 4 X 4 크기의 보드에서 즐기는 게임
한 번의 이동은 보드 위 전체블록을 상하좌우 중 하나로 이동
같은 값 두 블록 충돌 -> 하나로 합쳐짐
단 한 번의 이동에서 합쳐진 블록은 다시 합쳐짐 X
(블록 추가 X)
블록은 적어도 하나가 주어진다.

충돌의 의미?
같은 값을 갖는 두 블록 충돌 -> 합쳐진다.
세개 붙어있으면, 이동하려는 쪽으로 부터 가까운애들이 먼저 합쳐진다.

5번 이동해서 만들 수 있는 가장 큰 블록의 값?

 

---

사고 과정

5번 이동, 상하좌우 랜덤하게 모든 경우의 수 구해서 최댓값 갱신하는 형태
-> 5번 이동 후 최대값 조사 -> 재귀적 구현 + 이전 게임보드의 값을 저장해둬야함


충돌의 우선순위 파악
-> 이동 방향 기준으로 가까운 쪽부터 같은 것이 있는 지 조사

해당 지점이 0일 경우
-> 다음 충돌 가능성 조사

 

---

코드 구현

import java.util.Scanner;

public class EASY {
    static int Max, cnt;
    static int N;

    static int[][] board;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        Max = 0;
        board = new int[N][N];

        cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int num = sc.nextInt();
                board[i][j] = num;
            }
        }
        settle(0);
        System.out.println(Max);
    }

    //상하좌우에 따라 충돌 + 움직이는 메서드
    private static void settle(int circulation_num) {
        if (circulation_num >= 5) { //5개 돌았으면 됐어
            searchMax();
            return;
        }
        //가장 중요한 부분, 움직이기 전 게임판의 정보를 저장해두기
        int[][] copy = new int[N][N];
        for (int i = 0; i < N; i++)
            copy[i] = board[i].clone();

        for (int dir = 0; dir < 4; dir++) { //상우하좌
            game(dir);
            settle(circulation_num + 1);
            for (int i = 0; i < N; i++)
                board[i] = copy[i].clone();
            //게임 판을 이전걸로 돌려놔야돼

        }
    }


    private static void game(int dir) {

        move(dir); //먼저 해당 부분으로 다 옮긴 다음 충돌을 보자
        
        if (dir == 0) { //상
            for (int j = 0; j < N; j++) {//한 열씩 들어가보자
                for (int i = 0; i < N - 1; i++) { //한 행씩 볼거다
                    if (board[i][j] == 0) continue;

                    if (board[i + 1][j] == board[i][j]) {
                        int num1 = board[i][j];
                        board[i][j] = num1 + num1;
                        board[i + 1][j] = 0;
                    }
                }
            }
        } else if (dir == 1) { //우
            for (int i = 0; i < N; i++) {//한 열씩 들어가보자
                for (int j = N - 1; j > 0; j--) { //한 행씩 볼거다
                    if (board[i][j] == 0) continue;

                    if (board[i][j - 1] == board[i][j]) {
                        int num1 = board[i][j];
                        board[i][j] = num1 + num1;
                        board[i][j - 1] = 0;
                    }
                }
            }
        } else if (dir == 2) { //하
            for (int j = 0; j < N; j++) {//한 열씩 들어가보자
                for (int i = N - 1; i > 0; i--) { //한 행씩 볼거다
                    if (board[i][j] == 0) continue;

                    if (board[i - 1][j] == board[i][j]) {
                        int num1 = board[i][j];
                        board[i][j] = num1 + num1;
                        board[i - 1][j] = 0;
                    }
                }
            }
        } else if (dir == 3) { //좌
            for (int i = 0; i < N; i++) {//한 열씩 들어가보자
                for (int j = 0; j < N - 1; j++) { //한 행씩 볼거다
                    if (board[i][j] == 0) continue;
                    if (board[i][j + 1] == board[i][j]) {
                        int num1 = board[i][j];
                        board[i][j] = num1 + num1;
                        board[i][j + 1] = 0;
                    }
                }
            }
        }
        move(dir); // 0으로 채워진 부분이 있으니 이를 같은 방향으로 밀어서 마무리하기
    }

    private static void move(int dir) { //상우하좌
        if (dir == 0) { //상
            for (int c = 0; c < N; c++) {
                for (int r = 0; r < N; r++) {
                    if (board[r][c] == 0) {
                        int delta = 1;
                        while (r + delta < N) {
                            if (board[r + delta][c] == 0) {
                                delta++;
                                continue; // 또 0 만났으면 돌아가야지
                            }
                            if (board[r + delta][c] != 0) { //0 이 아니네!
                                board[r][c] = board[r + delta][c]; //자리 넣어주고
                                board[r + delta][c] = 0; //넌 0으로가라
                                break;
                            }
                        }
                    }
                }
            }
        } else if (dir == 1) { //우
            for (int r = 0; r < N; r++) {
                for (int c = N - 1; c >= 0; c--) {
                    if (board[r][c] == 0) {
                        int delta = 1;
                        while (c - delta >= 0) {
                            if (board[r][c - delta] == 0) {
                                delta++;
                                continue; // 또 0 만났으면
                            }
                            if (board[r][c - delta] != 0) { //0 이 아니네!
                                board[r][c] = board[r][c - delta]; //자리 넣어주고
                                board[r][c - delta] = 0; //넌 0으로가라
                                break;
                            }
                        }
                    }
                }
            }

        } else if (dir == 2) { //하
            for (int c = 0; c < N; c++) {
                for (int r = N - 1; r >= 0; r--) {
                    if (board[r][c] == 0) {
                        int delta = 1;
                        while (r - delta >= 0) {
                            if (board[r - delta][c] == 0) {
                                delta++;
                                continue; // 또 0 만났으면
                            }
                            if (board[r - delta][c] != 0) { //0 이 아니네!
                                board[r][c] = board[r - delta][c]; //자리 넣어주고
                                board[r - delta][c] = 0; //넌 0으로가라
                                break;
                            }
                        }
                    }
                }
            }
        } else if (dir == 3) {//좌
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (board[r][c] == 0) {
                        int delta = 1;
                        while (c + delta < N) {
                            if (board[r][c + delta] == 0) {
                                delta++;
                                continue; // 또 0 만났으면
                            }
                            if (board[r][c + delta] != 0) { //0 이 아니네!
                                board[r][c] = board[r][c + delta]; //자리 넣어주고
                                board[r][c + delta] = 0; //넌 0으로가라
                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    static void searchMax() { //최대값 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] > Max) {
                    Max = board[i][j];
                }
            }
        }
    }
}

---

회고록

• 이전 게임판의 정보를 가져오는 과정에서 원활하게 생각하지 못했음

👉 단순히 재귀함수 for문 안에 이전 정보를 가져오는 것으로 처음엔 코드를 구현했으나, 이는 움직임 방향 순서가 (상, 상, 상, 우, 좌)에서 (상, 상, 상, 하, 상)으로 바뀔 경우, (상,상,상 )까지 게임 판의 정보를 가져오는 것이 아닌 직전의 순서인 (상, 상, 상, 우, 좌) 의 정보를 가져오며 의미없는 되돌리기 형태로 사용됨.

 

해당 스택 데이터 특성을 활용, copy 2차원 배열을 선언함으로써 해결