백준 알고리즘 12100번 2048 풀이 with Python

문제 링크: https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

백준 알고리즘 12100번 2048

2048에서 구현해야 될 가장 중요한 요소는 판을 상하좌우로 움직였을 때 제대로 구현하는 것이 가장 중요하고, 이후에는 5번 움직이는 것을 구현하는 것이 중요하였다. 나는 sub라는 함수로 상하좌우를 움직였을 때 판의 최댓값과 판의 배열 상태를 return 하도록 하였고, solution 함수를 이용하여 상하좌우로 5번 움직여서 최댓값을 리턴하도록 하는 함수를 구현하였다.  다음은 이를 구현한 코드이다.

 

from copy import deepcopy


def sub(map111, d, n):
    make = []
    maxi = 0
    map2 = deepcopy(map111)
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    if d == 0 or d == 1:
        a = range(n)
        b = range(n)
    else:
        a = range(n - 1, -1, -1)
        b = range(n - 1, -1, -1)
    for i in a:
        for j in b:
            if map2[i][j] == 0:
                continue
            else:
                if maxi < map2[i][j]:
                    maxi = map2[i][j]
                nx = i
                ny = j
                while 1:
                    nx += dx[d]
                    ny += dy[d]
                    # 탐색한 점이 보드판 위의 점일 때
                    if -1 < nx < n and -1 < ny < n:
                        # 합칠 수 있을 때
                        if map2[nx][ny] == map2[i][j] and [nx, ny] not in make:
                            map2[nx][ny] *= 2
                            map2[i][j] = 0
                            if maxi < map2[nx][ny]:
                                maxi = map2[nx][ny]
                            make.append([nx, ny])
                            break
                        # 값은 같으나 합칠 수 없을 때 또는 값이 다르고 0이 아닐 때
                        elif map2[nx][ny] == map2[i][j] or (map2[nx][ny] != map2[i][j] and map2[nx][ny] != 0):
                            map2[nx - dx[d]][ny - dy[d]] = map2[i][j]
                            if nx - dx[d] == i and ny - dy[d] == j:
                                break
                            else:
                                map2[i][j] = 0
                            break
                        # 탐색값이 0일 때는 계속 전진
                        elif map2[nx][ny] == 0:
                            continue
                    # 맵의 범위를 넘어갈 때
                    else:
                        nx -= dx[d]
                        ny -= dy[d]
                        if nx == i and ny == j:
                            break
                        else:
                            map2[nx][ny] = map2[i][j]
                            map2[i][j] = 0
                            break
    return map2, maxi


def solution(map11, n):
    global answer
    stack = []
    stack.append([[map11, 0], 0])
    while stack:
        result, count = stack.pop()
        if count == 5:
            if result[1] > answer:
                answer = result[1]
        else:
            for w in range(4):
                stack.append([sub(result[0], w, n), count + 1])


n = int(input())
map1 = [list(map(int, input().split())) for _ in range(n)]
answer = 0
solution(map1, n)
print(answer)