[백준] 12110번 2048 (Easy) (Java)

✅ 문제

12110번 2048 (Easy)

12100번: 2048 (Easy)

---

✅ 풀이

import java.io.*;
import java.util.*;

public class Main {
    private static class Block {
        public Block(long num, int count) {
            this.num = num;
            this.count = count;  // 몇 번째 이동에서 움직였는지 확인할 변수
        }

        long num;
        int count;

        public Block clone() {
            return new Block(this.num, this.count);
        }
    }

    private static int N;
    private static long MAX_NUM;
    private static Block[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());  // MAP의 크기
        map = new Block[N][N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = new Block(Long.parseLong(st.nextToken()), -1);  // 이동 번호를 -1로 초기화
            }
        }

        start(map, 0);  // 게임 시작
        System.out.println(MAX_NUM);
    }

    private static void start(Block[][] map, int count) {
        if (5 <= count) {  // 게임 다섯 번 모두 진행 했을 시
            //printMap(map);
            return;
        }
        Block[][] tmpMap = new Block[N][N];

        copyMap(map, tmpMap);  // 맵 복사
        moveUp(tmpMap, count);  // 위로 움직여 보기
        start(tmpMap, count + 1);  // 다음 게임

        copyMap(map, tmpMap);  // 맵 복사
        moveDown(tmpMap, count);  // 아래로 움직여 보기
        start(tmpMap, count + 1);  // 다음 게임

        copyMap(map, tmpMap);  // 맵 복사
        moveLeft(tmpMap, count);  // 왼쪽으로 움직여 보기
        start(tmpMap, count + 1);  // 다음 게임

        copyMap(map, tmpMap);  // 맵 복사
        moveRight(tmpMap, count);  // 오른쪽으로 움직여 보기
        start(tmpMap, count + 1);  // 다음 게임
    }

    private static void moveUp(Block[][] map, int count) {
        int r;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j].num != 0) {
                    r = i;
                    while (0 <= r - 1 && map[r - 1][j].num == 0) {  // 움직이려는 방향이 빈칸일 때까지
                        map[r - 1][j].num = map[r][j].num;
                        map[r--][j].num = 0;
                    }
                    if (0 <= r - 1 && map[r - 1][j].num == map[r][j].num && map[r - 1][j].count != count) {  // 합치기
                        map[r - 1][j].num *= 2;
                        map[r - 1][j].count = count;
                        map[r--][j].num = 0;
                    }
                    while (0 <= r - 1 && map[r - 1][j].num == 0) {  // 움직이려는 방향이 빈칸일 때까지
                        map[r - 1][j] = map[i][j].clone();
                        map[r--][j].num = 0;
                    }
                    MAX_NUM = Math.max(MAX_NUM, map[r][j].num);
                }
            }
        }
    }

    private static void moveDown(Block[][] map, int count) {
        int r;
        for (int i = N - 1; 0 <= i; i--) {
            for (int j = N - 1; 0 <= j; j--) {
                if (map[i][j].num != 0) {
                    r = i;
                    while (r + 1 < N && map[r + 1][j].num == 0) {  // 움직이려는 방향이 빈칸일 때까지
                        map[r + 1][j].num = map[r][j].num;
                        map[r++][j].num = 0;
                    }
                    if (r + 1 < N && map[r + 1][j].num == map[r][j].num && map[r + 1][j].count != count) {  // 합치기
                        map[r + 1][j].num *= 2;
                        map[r + 1][j].count = count;
                        map[r++][j].num = 0;
                    }
                    while (r + 1 < N && map[r + 1][j].num == 0) {  // 움직이려는 방향이 빈칸일 때까지
                        map[r + 1][j] = map[i][j].clone();
                        map[r++][j].num = 0;
                    }
                    MAX_NUM = Math.max(MAX_NUM, map[r][j].num);
                }
            }
        }
    }

    private static void moveLeft(Block[][] map, int count) {
        int c;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j].num != 0) {
                    c = j;
                    while (0 <= c - 1 && map[i][c - 1].num == 0) {  // 움직이려는 방향이 빈칸일 때까지
                        map[i][c - 1].num = map[i][c].num;
                        map[i][c--].num = 0;
                    }
                    if (0 <= c - 1 && map[i][c - 1].num == map[i][c].num && map[i][c - 1].count != count) {  // 합치기
                        map[i][c - 1].num *= 2;
                        map[i][c - 1].count = count;
                        map[i][c--].num = 0;
                    }
                    while (0 <= c - 1 && map[i][c - 1].num == 0) {  // 움직이려는 방향이 빈칸일 때까지
                        map[i][c - 1] = map[i][j].clone();
                        map[i][c--].num = 0;
                    }
                    MAX_NUM = Math.max(MAX_NUM, map[i][c].num);
                }
            }
        }
    }

    private static void moveRight(Block[][] map, int count) {
        int c;
        for (int i = N - 1; 0 <= i; i--) {
            for (int j = N - 1; 0 <= j; j--) {
                if (map[i][j].num != 0) {
                    c = j;
                    while (c + 1 < N && map[i][c + 1].num == 0) {  // 움직이려는 방향이 빈칸일 때까지
                        map[i][c + 1].num = map[i][c].num;
                        map[i][c++].num = 0;
                    }
                    if (c + 1 < N && map[i][c + 1].num == map[i][c].num && map[i][c + 1].count != count) {  // 합치기
                        map[i][c + 1].num *= 2;
                        map[i][c + 1].count = count;
                        map[i][c++].num = 0;
                    }
                    while (c + 1 < N && map[i][c + 1].num == 0) {  // 움직이려는 방향이 빈칸일 때까지
                        map[i][c + 1] = map[i][j].clone();
                        map[i][c++].num = 0;
                    }
                    MAX_NUM = Math.max(MAX_NUM, map[i][c].num);
                }
            }
        }
    }

    private static void copyMap(Block[][] map, Block[][] tmpMap) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                tmpMap[i][j] = map[i][j].clone();
            }
        }
    }
}

 

🧩 블록은 어떻게 움직이는가?

내가 느꼈을 때 이 문제의 가장 헷갈렸던 점은 블록의 움직이는 방향이었다.

직접 게임을 즐겨보고 나서야 (재미있어서 한 거 아님) 내가 고민했던 부분을 해결할 수 있었다.

 

2

2

4

 

위와 같은 블록이 존재할 때,  왼방향으로 한 번 이동하게 된다면 블록은 어떻게 바뀔까?

 

4

4

0

 

위와 같이 바뀔 것이다. 문제에서 나와있듯이, 한 번 이동된 블록은 다시 합칠 수 없기 때문이다.

그렇다면 왼방향이 아닌, 오른방향으로 한 번 이동하게 된다면 블록은 어떻게 바뀌게 될까?

 

0

0

8

0

4

4

 

위 두 가지의 경우를 생각해볼 수 있다.

1. 0 0 8 같은 경우에는 가장 오른쪽의 4는 이동하지 않았고 가장 왼쪽의 2를 가운데의 2와 합쳐 4를 만들고, 오른쪽의 4와 합쳐 8을 만들 수 있다고 생각할 수 있다.

2. 반면 0 4 4의 경우에는 가장 오른쪽의 4는 이동하지 않고, 가운데의 2 또한 따로 이동하지 않고, 2를 한 번 이동시켜 4를 만든다. 이미 한 번의 이동에서 4로 합쳐졌기 때문에 4와 4는 합치지 않는다.

 

정답은 2번이다. 필자는 전자로 생각하여 4%에서 틀렸다...

 

한 번 합쳐지는 것에 대한 개념이 중요할 것 같다.

8로 합쳐지는 과정까지가 왼쪽의 2가 한 번 합쳐지는 과정이라고 생각했으나, 

2 2 가 4로 합쳐지는 과정이 한 번 합쳐진 블록이고

이 이후에 다음 블록으로는 합쳐지지 못한다는 것이다.

 

이 외의 다른 예외 케이스들에 대해서는 질문 게시판에 상세히 나와있으니 아래와 같이 간략하게 설명하겠다.

• 블록을 뛰어넘어 합쳐지는 경우
• 합쳐지는 순서가 잘못되었을 경우 (예를 들어 2 2 2를 왼방향 이동했을 때, 2 4 0이 되는 등

블록이 이동되는 방향을 각각 출력해보며 확인해보길 바란다.