[BOJ][🟡2][백준#12100] 2048 (Easy)

문제 출처

BAEKJOON Online Judge #12100

문제

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번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

예제

입력

3
2 2 2
4 4 4
8 8 8

출력

16

My Sol

def shift_line(arr):
    global N
    def find_initial_blank(arr):
        global N
        i = 0
        while i < N:
            if arr[i]: i += 1
            else: return i
        return N

    def pull_nums(j, ni, arr):
        global N
        while j < N:
            if arr[j]:
                arr[ni] = arr[j]
                arr[j] = 0
                ni += 1
            j += 1
        return arr

    def combine(arr):
        global N
        j = 1
        while j < N:
            if arr[j] == arr[j-1]:
                arr[j] = 0
                arr[j-1] *= 2
                j += 1
            j += 1
        return arr

    j = ni = find_initial_blank(arr)
    arr = pull_nums(j, ni, arr)
    arr = combine(arr)
    j = ni = find_initial_blank(arr)
    return pull_nums(j, ni, arr)


def DFS(mat, depth):
    global N, total_max
    if depth == 5:
        cur_max = 0
        for i in range(N):
            for j in range(N):
                if cur_max < mat[i][j]:
                    cur_max = mat[i][j]
        total_max = max(total_max, cur_max)
        return

    DFS(LEFT([line[:] for line in mat]), depth+1)
    DFS(RIGHT([line[:] for line in mat]), depth+1)
    DFS(UP([line[:] for line in mat]), depth+1)
    DFS(DOWN([line[:] for line in mat]), depth+1)


def LEFT(mat):
    global N
    for i in range(N):
        mat[i] = shift_line(mat[i])
    return mat

def RIGHT(mat):
    global N
    for i in range(N):
        mat[i] = shift_line(mat[i][::-1])[::-1]
    return mat

def UP(mat):
    global N
    new_mat = [[0]*N for _ in range(N)]
    for j in range(N):
        arr = []
        for i in range(N):
            arr.append(mat[i][j])
        arr = shift_line(arr)
        for i in range(N):
            new_mat[i][j] = arr[i]
    return new_mat

def DOWN(mat):
    global N
    new_mat = [[0]*N for _ in range(N)]
    for j in range(N):
        arr = []
        for i in range(N):
            arr = [mat[i][j]] + arr
        arr = shift_line(arr)
        for i in range(N):
            new_mat[i][j] = arr.pop()
    return new_mat


N = int(input())
mat_origin = [list(map(int, input().split())) for _ in range(N)]
mat = [line[:] for line in mat_origin]

total_max = 0
DFS(mat, 0)
print(total_max)

이전에 실패했던 빡센 구현문제였다. 우선 총 5회의 시도를 생각해보았을 때, 상하좌우의 이동 4가지의 5제곱이라면 1024, 약 1000회의 브루트포스가 가능하다고 판단되었다. 이는 곧 depth가 최대 5인 DFS로 상황을 모두 무작정 시도하여 최댓값을 파악하는 것이다.

핵심은 2차원 배열에서 어떠한 이동이든 한 라인마다의 동작으로 쪼개서 생각해볼 수 있다는 것이다. 즉, 상하좌우 어떠한 이동이든 라인을 기준으로 하여 미루고 합쳐진 결과 라인을 다시 반환하는 함수를 만들고, 이를 적절히 가공하여 모든 방향에 대한 결과를 나타낼 수 있겠다고 판단하였다.

1. 입력을 처리하여 2차원 배열 mat을 만든다.
2. DFS 함수에 mat을 넣어준다.
3. DFS 함수는 depth가 5가 되면 더이상의 진행을 하지 않고 mat 내부의 최댓값을 판단하여 전역 total_max를 갱신한다.
4. DFS 함수는 상하좌우 동작의 결과 2차원 배열을 다음 DFS 함수에 재귀적으로 인자로 전달한다.
5. 상하좌우 동작에 해당하는 LEFT RIGHT UP DOWN 에 각각 2차원 배열의 깊은 복사 버전을 전달하여 동작의 결과물을 반환시키고, 이를 depth가 하나 더 추가된 DFS 함수에 바로 전달하여 재귀적으로 확인한다.

주의할 점은 인자로 넘어와 상하좌우의 동작에 각각 전달될 mat 2차원 배열은 깊은 복사를 활용한 별개의 mat으로 전달해야 한다는 것이다. 만약 그렇지 않다면 왼쪽으로 동작을 미룬 mat이 그대로 다음 RIGHT에 전달되기 때문이다. 이는 우리가 기대하는 독립적인 동작과는 거리가 멀다.

브루트포스이지만 백트래킹을 충분히 염두에 둘 수 있다.

백트래킹 1. 이동 전과 후의 mat 상태가 같다면 더이상의 같은 이동은 무의미하다. 백트래킹 2. 현재 depth와 최대 depth, 그리고 현재 최댓값과 전역의 최댓값을 비교해서 2**(depth차이)만큼 차이가 나지 않으면 그 이후의 어떠한 이동에도 최댓값을 넘어설 수 없다. 왜냐하면 한 번 이동으로 2배 이상 커질 수 없기 때문이다.

백트래킹 요소가 보이지만 일단 브루트포스로 풀었는데 시간 내에 잘 해결되어서 더 이상의 백트래킹을 활용한 최적화는 불필요하였다.

결과

맞았습니다!!

모범답안

출처

# empty