[백준] 12100번 2048(Easy) - Python / 알고리즘 중급 1/3 - 브루트 포스 - 비트마스크 (연습)

---

---

---

💡 문제

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

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

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

---

💭 접근

보드의 숫자들을 상하좌우로 움직이며 백트래킹 기법을 사용하여 보드를 deepcopy를 사용하여 복사하며 5번 움직였을 때의 최댓값을 구하는 문제이다.

이때 게임의 규칙에 따라 어떻게 하면 숫자들을 움직일 수 있을까?
상하좌우 모두 코드는 비슷하기에 왼쪽으로 움직이는 함수를 하나 살펴보자.

def left(copied_board):
    for i in range(n):
        cursor = 0
        for j in range(1, n):
            if copied_board[i][j] != 0:
                num = copied_board[i][j]
                copied_board[i][j] = 0

                if copied_board[i][cursor] == 0:
                    copied_board[i][cursor] = num
                elif copied_board[i][cursor] == num:
                    copied_board[i][cursor] *= 2
                    cursor += 1
                else:
                    cursor += 1
                    copied_board[i][cursor] = num
    return copied_board

먼저 보드가 위와 같은 상태라고 가정하고, 현재 2번째 행에 대하여 숫자를 움직여야하는 상태라고 보자.

먼저 노란색 칸이 cursor로, 이는 다음 숫자가 올 칸이라고 할 수 있다.
또한 초록색 칸은 for문에서 i, j가 가리키는 숫자이다.

초기의 cursor 값은 0이므로 가장 왼쪽에 위치하며, copied_board[i][j]가 0이 아니므로 num은 2가 되고, 움직여야 하는 숫자가 된다.

이때 copied_board[i][j]는 2로, 왼쪽으로 움직일 시 비워져야 하므로 0으로 바뀌고, cursor가 가리키는 칸의 숫자가 0이므로 이 칸은 num 즉, 2가 된다.

이와 같은 작업을 조건에 따라 반복하면 다음과 같은 순서로 이루어진다.

이처럼 모든 방향에 대해 이와 같은 작업을 5번 거친 후, 만들 수 있는 최대값을 출력하면 된다.

---

📒 코드

import copy

def dfs(depth, board):
    global ans

    if depth == 5:
        for i in range(n):
            ans = max(ans, max(board[i]))
        return

    for direction in ('u', 'd', 'l', 'r'):
        tmp = copy.deepcopy(board)

        if direction == 'u':
            dfs(depth + 1, up(tmp))
        elif direction == 'd':
            dfs(depth + 1, down(tmp))
        elif direction == 'l':
            dfs(depth + 1, left(tmp))
        elif direction == 'r':
            dfs(depth + 1, right(tmp))

def up(copied_board):
    for j in range(n):
        cursor = n - 1
        for i in range(n - 2, -1, -1):
            if copied_board[i][j] != 0:
                num = copied_board[i][j]
                copied_board[i][j] = 0

                if copied_board[cursor][j] == 0:
                    copied_board[cursor][j] = num
                elif copied_board[cursor][j] == num:
                    copied_board[cursor][j] *= 2
                    cursor -= 1
                else:
                    cursor -= 1
                    copied_board[cursor][j] = num
    return copied_board

def down(copied_board):
    for j in range(n):
        cursor = 0
        for i in range(1, n):
            if copied_board[i][j] != 0:
                num = copied_board[i][j]
                copied_board[i][j] = 0

                if copied_board[cursor][j] == 0:
                    copied_board[cursor][j] = num
                elif copied_board[cursor][j] == num:
                    copied_board[cursor][j] *= 2
                    cursor += 1
                else:
                    cursor += 1
                    copied_board[cursor][j] = num
    return copied_board

def left(copied_board):
    for i in range(n):
        cursor = n - 1
        for j in range(n - 2, -1, -1):
            if copied_board[i][j] != 0:
                num = copied_board[i][j]
                copied_board[i][j] = 0

                if copied_board[i][cursor] == 0:
                    copied_board[i][cursor] = num
                elif copied_board[i][cursor] == num:
                    copied_board[i][cursor] *= 2
                    cursor -= 1
                else:
                    cursor -= 1
                    copied_board[i][cursor] = num
    return copied_board

def right(copied_board):
    for i in range(n):
        cursor = 0
        for j in range(1, n):
            if copied_board[i][j] != 0:
                num = copied_board[i][j]
                copied_board[i][j] = 0

                if copied_board[i][cursor] == 0:
                    copied_board[i][cursor] = num
                elif copied_board[i][cursor] == num:
                    copied_board[i][cursor] *= 2
                    cursor += 1
                else:
                    cursor += 1
                    copied_board[i][cursor] = num
    return copied_board

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

ans = 0
dfs(0, graph)

print(ans)

---

💭 후기

힌트를 보고도 해결하지 못했고, 이해하는데 많은 시간이 걸렸던 문제였다. 계속해서 복습해야겠다.

---

🔗 문제 출처

https://www.acmicpc.net/problem/12100

---