백준 12094 - 2048 (Hard) [파이썬]

풀이

이전에 풀었던 2048 (Easy) 문제의 풀이 방법에서는 모든 경우의 수를 탐색하여 답을 도출했다면 2048 (Hard)는 10회의 이동으로 확장되었기 때문에 적절히 가지치기를 하여 시간을 줄여 답을 도출해야 합니다. 그럼, 어떤 경우를 가지치기해주어야 할까요?

 

 

• 블록들을 이동시켰는데 이전과 같은 모습일 경우

단순하게 생각해봤을 때 가장 먼저 떠오르는 방법입니다.

 

어떤 한 경우에 대하여 상하좌우를 모두 구하기 때문에 상하좌우 중 같은 모양을 가진 경우가 발생하면 애초에 탐색할 필요가 없습니다. 중복된 경우를 탐색하기 때문입니다.

 

 

• 구한 최댓값이 이전에 구한 것보다 작을 것이라는 게 예상되는 경우

이 경우는 저도 백준 질문 검색에서 얻어낸 해답입니다.

 

예를 들어 처음에 최대 10회 이동에 대해 탐색하였더니 512라는 수가 최댓값이 되었다고 합시다. 그럼 2048 게임 특성에 의해 9회 이동에는 적어도 최댓값이 256이 되었을 것이고, 8회 이동에는 128, 7회 이동에는 64와 같이 이동 횟수가 1회 감소할 때마다 최댓값이 적어도 절반씩 작아졌음을 예상할 수 있습니다.

 

그러면, 어떤 경우의 10회 최댓값을 구하면 1회까지의 예측되는 최댓값을 기록할 수 있게 되고 어떤 n회 이동의 경우에서의 최댓값이 아까 구한 1~10회까지의 예측되는 최댓값의 n회 최댓값 보다 작다면 버릴 수 있게 됩니다.

 

코드로 보이면 다음과 같습니다.

max_num = 0
# 현재 n회 이동에서의 최댓값을 구하여
for i in range(N):
    max_num = max(max_num, max(board[i]))
# 이전에 구했던 n회 이동의 최댓값보다 작다면 현재 경우의 수는 어떻게 이동하던간에
# 이전에 구한 최댓값보다 작다.
if (max_num <= max_list[deep]): return

원래대로라면 이 두 경우만 잘 구현하면 성공입니다.

 

근데 저 같은 경우는 이전에 풀었던 '2048 (Easy)'에서 보드를 움직이는 알고리즘을 삼중 for문으로 구현하여서 자꾸 10%에서 시간 초과가 났었습니다. 그래서 처음엔 가지치기가 문제인 줄 알았는데 삼중 for문이 문제였고 이중 for문으로 해결하였습니다.

 

저처럼 삼중이 아니라 이중 for문으로 만드셨다면 애초에 문제없이 될 것 같습니다!!

 

코드

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
mNum = 0
for i in range(N):
    mNum = max(mNum, max(board[i]))
max_num = 0
max_list = [0 for _ in range(11)]

def board_move(wasd):
    if (wasd == 0): # 위
        for column in range(N):
            top = 0
            for row in range(1, N):
                if board[row][column] != 0:
                    temp = board[row][column]
                    board[row][column] = 0
                
                    if board[top][column] == 0:
                        board[top][column] = temp
                    elif board[top][column] == temp:
                        board[top][column] <<= 1
                        top += 1
                    else:
                        top += 1
                        board[top][column] = temp
    elif (wasd == 1): # 아래
        for column in range(N):
            top = N-1
            for row in range(N-2, -1, -1):
                if board[row][column] != 0:
                    temp = board[row][column]
                    board[row][column] = 0
                
                    if board[top][column] == 0:
                        board[top][column] = temp
                    elif board[top][column] == temp:
                        board[top][column] <<= 1
                        top -= 1
                    else:
                        top -= 1
                        board[top][column] = temp
    elif (wasd == 2): # 왼쪽
        for row in range(N):
            top = 0
            for column in range(1, N):
                if board[row][column] != 0:
                    temp = board[row][column]
                    board[row][column] = 0
                
                    if board[row][top] == 0:
                        board[row][top] = temp
                    elif board[row][top] == temp:
                        board[row][top] <<= 1
                        top += 1
                    else:
                        top += 1
                        board[row][top] = temp
    elif (wasd == 3):
        for row in range(N):
            top = N-1
            for column in range(N-2, -1, -1):
                if board[row][column] != 0:
                    temp = board[row][column]
                    board[row][column] = 0
                
                    if board[row][top] == 0:
                        board[row][top] = temp
                    elif board[row][top] == temp:
                        board[row][top] <<= 1
                        top -= 1
                    else:
                        top -= 1
                        board[row][top] = temp

def n_2048(deep):
    global mNum, board, max_num

    max_num = 0
    for i in range(N):
        max_num = max(max_num, max(board[i]))
    if (max_num <= max_list[deep]): return

    if (deep == 10):
        mNum = max(mNum, max_num)
        max_num = mNum
        if (max_list[10] < max_num):
            for i in range(10, 0, -1):
                max_list[i] = max_num
                max_num //= 2
        return
    
    bd = [b[:] for b in board]
    for i in range(4):
        board_move(i)
        if (bd == board):
            continue
        n_2048(deep + 1)
        board = [b[:] for b in bd]

n_2048(0)
print(mNum)