[백트래킹, 시뮬레이션] BOJ 12100 2048(easy)

import sys
import copy
input = sys.stdin.readline
 
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
 
def move_left(n, board):
    for i in range(n):
        p = 0
        for j in range(1, n):
            if not board[i][j]: continue 
            tmp = board[i][j]
            board[i][j] = 0
            if board[i][p] == 0:
                board[i][p] = tmp
            elif board[i][p] == tmp:
                board[i][p] *= 2 
                p += 1
            else:
                p += 1
                board[i][p] = tmp
                
    return board
           
        
def move_right(n, board):
    for i in range(n):
        p = n - 1
        for j in range(n - 2, -1, -1):
            if not board[i][j]: continue 
            tmp = board[i][j]
            board[i][j] = 0
            if board[i][p] == 0:
                board[i][p] = tmp
                board[i][j] = 0
            elif board[i][p] == tmp:
                board[i][p] *= 2
                board[i][j] = 0
                p -= 1
            else:
                p -= 1
                board[i][p] = tmp
    return board
 
def move_up(n, board):
    for j in range(n):
        p = n - 1 
        for i in range(n - 2, -1, -1):
            if not board[i][j]: continue
            tmp = board[i][j]
            board[i][j] = 0
            if board[p][j] == 0:
                board[p][j] = tmp
            elif board[p][j] == tmp:
                board[p][j] *= 2
                board[i][j] = 0
                p -= 1
            else:
                p -= 1
                board[p][j] = tmp
    return board         
         
def move_down(n, board):
    for j in range(n):
        p = 0
        for i in range(1, n):
            if not board[i][j]: continue
            tmp = board[i][j]
            board[i][j] = 0
            if board[p][j] == 0:
                board[p][j] = tmp
                board[i][j] = 0
            elif board[p][j] == tmp:
                board[p][j] *= 2
                board[i][j] = 0
                p += 1
            else:
                p += 1
                board[p][j] = tmp
    return board
 
def backtracking(n, depth, board):
    global result
    if depth == 5:
        return max([max(row) for row in board])
 
    # 매 순간마다 left, right, up, down 결과 중 최댓값으로 고르게 함
    return max(backtracking(n, depth+1, move_left(n, copy.deepcopy(board))), 
               backtracking(n, depth+1, move_right(n, copy.deepcopy(board))),
               backtracking(n, depth+1, move_up(n, copy.deepcopy(board))),
               backtracking(n, depth+1, move_down(n, copy.deepcopy(board))))   
 
        
print(backtracking(N, 0, copy.deepcopy(board)))