[백준 12100번] 파이썬 - 2048

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

12100번: 2048 (Easy)

# 조건

• 2048 게임은 4x4 크기의 보드에서 혼자 즐기는 게임
• 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다.
• 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다.
• 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
• 이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다.
• 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

 

# 접근 방법

• 백트래킹을 이용한 브루트포스로 풀어준다.
• 움직일 수 있는 방향이 동, 서, 남, 북 4가지이다.
• 이 때, 동쪽으로 움직인다면 모든 행에 대해 n-1 칸부터 0번째까지 동쪽으로 움직이는 것을 구현
• 현재 움직이려는 블록의 동쪽 마지노선의 블록이 현재 블록과 같은 수라면 수를 더해준 후 마지노선 칸에 그 수를 넣어주고 현재 블록은 0으로 만들어 다음 블록들이 이동할 수 있도록 만든다.
  • ( 0 0 2 2 = > 0 0 0 4 )
• 마지노선 블록이 0이라면 그 칸을 현재 블록의 숫자로 대체한 후 현재 블록을 0으로 만든다.
• 마지노선이 현재 블록과 같은 수가 아니라면, 합칠 수가 없기 때문에 마지노선을 하나 당긴다.
• 여기서 말하는 마지노선이란, 처음에는 동쪽 가장 끝이 될 것이며 동쪽 가장 끝이 이미 계산이 된 상태라면 -1씩 해주어 마지노선을 하나씩 줄여주는 것을 말한다.
• 그리고, 동쪽으로 움직인 경우를 만든 후에 서쪽으로 움직일 때는 동쪽으로 움직인 게임판을 이어서 이용하는 것이 아니라 동쪽으로 움직이기 전의 게임판을 서쪽으로 움직여야 하기 때문에 깊은복사(DeepCopy)를 통해 기존 맵을 복사해둔 후에 그 맵을 이동하도록 한다.

from copy import deepcopy  
  
n = int(input())  
  
graph = []  
for i in range(n):  
    graph.append(list(map(int, input().split())))  
  
def move(board, dir):  
    if dir == 0:  # 동쪽  
        for i in range(n):  
            top = n - 1  
            for j in range(n - 2, -1, -1):  
                if board[i][j]:  
                    tmp = board[i][j]  
                    board[i][j] = 0  
                    if board[i][top] == 0:  
                        board[i][top] = tmp  
                    elif board[i][top] == tmp:  
                        board[i][top] = tmp * 2  
                        top -= 1  
                    else:  
                        top -= 1  
                        board[i][top] = tmp  
  
    elif dir == 1:  # 서쪽  
        for i in range(n):  
            top = 0  
            for j in range(1, n):  
                if board[i][j]:  
                    tmp = board[i][j]  
                    board[i][j] = 0  
                    if board[i][top] == 0:  
                        board[i][top] = tmp  
                    elif board[i][top] == tmp:  
                        board[i][top] = tmp * 2  
                        top += 1  
                    else:  
                        top += 1  
                        board[i][top] = tmp  
  
    elif dir == 2:  # 남쪽  
        for j in range(n):  
            top = n - 1  
            for i in range(n - 2, -1, -1):  
                if board[i][j]:  
                    tmp = board[i][j]  
                    board[i][j] = 0  
                    if board[top][j] == 0:  
                        board[top][j] = tmp  
                    elif board[top][j] == tmp:  
                        board[top][j] = tmp * 2  
                        top -= 1  
                    else:  
                        top -= 1  
                        board[top][j] = tmp  
  
    else:  
        for j in range(n):  
            top = 0  
            for i in range(1, n):  
                if board[i][j]:  
                    tmp = board[i][j]  
                    board[i][j] = 0  
                    if board[top][j] == 0:  
                        board[top][j] = tmp  
                    elif board[top][j] == tmp:  
                        board[top][j] = tmp * 2  
                        top += 1  
                    else:  
                        top += 1  
                        board[top][j] = tmp  
  
    return board  
  
  
def dfs(board, cnt):  
    global ans  
    if cnt == 5:  
        for i in range(n):  
            for j in range(n):  
                ans = max(ans, board[i][j])  
        return  
  
    for i in range(4):  
        tmp_board = move(deepcopy(board), i)  
        dfs(tmp_board, cnt + 1)  
  
ans = 0  
dfs(graph, 0)  
print(ans)