Baekjoon 12100. 2048 (Easy) / Python

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

알고리즘 설명

2048 게임의 진행 방식을 최대 5번 시행해서 나오는 수의 최댓값을 찾아낸다.

상하좌우의 모든 방향에 대해 움직일 때, 블록의 이동과 블록이 합쳐지는 함수를 만들어내서, 5회 실행한다.

함수 실행횟수가 4 ** 5 로 약 1000번 밖에 안된다. 시행횟수가 많아진다면 다른 함수를 고안해야 할 듯..

import sys
from copy import deepcopy
input = sys.stdin.readline

# 보드 크기 n 
n = int(input())

# 보드 초기 상태
game = [list(map(int, input().split())) for _ in range(n)]
res = 0  # 결과값

# n이 1인 경우, 유일한 블록 값 출력
if n == 1:
    print(game[0][0])
    exit(0)

# 보드를 왼쪽으로 이동하는 함수
def left(brd):
    for i in range(n):
        now = 0
        for j in range(1, n):
            if brd[i][j] != 0:
                tmp = brd[i][j]
                brd[i][j] = 0

                if brd[i][now] == 0:
                    brd[i][now] = tmp

                elif brd[i][now] == tmp:
                    brd[i][now] *= 2
                    now += 1
                else:
                    now += 1
                    brd[i][now] = tmp
    return brd

# 보드를 오른쪽으로 이동하는 함수
def right(brd):
    for i in range(n):
        now = n - 1
        for j in range(n - 1, -1, -1):
            if brd[i][j] != 0:
                tmp = brd[i][j]
                brd[i][j] = 0

                if brd[i][now] == 0:
                    brd[i][now] = tmp

                elif brd[i][now] == tmp:
                    brd[i][now] *= 2
                    now -= 1
                else:
                    now -= 1
                    brd[i][now] = tmp
    return brd

# 보드를 위쪽으로 이동하는 함수
def up(brd):
    for j in range(n):
        now = 0
        for i in range(n):
            if brd[i][j] != 0:
                tmp = brd[i][j]
                brd[i][j] = 0

                if brd[now][j] == 0:
                    brd[now][j] = tmp

                elif brd[now][j] == tmp:
                    brd[now][j] *= 2
                    now += 1
                else:
                    now += 1
                    brd[now][j] = tmp
    return brd

# 보드를 아래쪽으로 이동하는 함수
def down(brd):
    for j in range(n):
        now = n - 1
        for i in range(n - 1, -1, -1):
            if brd[i][j] != 0:
                tmp = brd[i][j]
                brd[i][j] = 0

                if brd[now][j] == 0:
                    brd[now][j] = tmp

                elif brd[now][j] == tmp:
                    brd[now][j] *= 2
                    now -= 1
                else:
                    now -= 1
                    brd[now][j] = tmp
    return brd

# DFS 탐색 함수
def dfs(c, arr):
    global res
    if c == 5:  # 최대 5번 이동
        res = max(max(map(max, arr)), res)  # 최대 블록 값 갱신
        return
    for i in range(4):
        copy_arr = deepcopy(arr)  # 보드 상태 복사
        if i == 0:
            dfs(c + 1, left(copy_arr))  # 왼쪽으로 이동
        elif i == 1:
            dfs(c + 1, right(copy_arr))  # 오른쪽으로 이동
        elif i == 2:
            dfs(c + 1, up(copy_arr))  # 위쪽으로 이동
        else:
            dfs(c + 1, down(copy_arr))  # 아래쪽으로 이동

# DFS 탐색 시작
dfs(0, game)

# 결과값 출력
print(res)