백준 12100 : 2048(Easy) [파이썬]

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

12100번: 2048 (Easy)

 

1. 문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

2. 문제 풀이

재귀로 4방향으로 모든 경우의 수를 다해본다 

어려운 점은 3가지 정도로 꼽을 수 있었다

1. 이동 하는 것 구현
2. 재귀로 모든 경우의 수 탐색
3. 탐색할 때 새로운 리스트 생성

이것들을 주의 하며 구현하면서 코드를 완성 했다.

from copy import deepcopy

def move(a, d, board):
    if d == 0:
        for i in range(a):
            cnt = 0
            for j in range(a - 1, -1, -1):
                if board[i][j]:
                    for jj in range(j + 1, a - cnt):
                        if board[i][j] == board[i][jj]:
                            board[i][j] = 0
                            board[i][jj] *= 2
                            cnt += 1
                            break

                        elif board[i][jj] and board[i][j] != board[i][jj]:
                            cnt += 1
                            save = board[i][j]
                            board[i][j] = 0
                            board[i][jj - 1] = save
                            break

                        elif jj == a - cnt - 1:
                            save = board[i][j]
                            board[i][j] = 0
                            board[i][jj] = save

    elif d == 1:
        for i in range(a):
            cnt = 0
            for j in range(a):
                if board[i][j]:
                    for jj in range(j - 1, -1 + cnt, -1):
                        if board[i][j] == board[i][jj]:
                            board[i][j] = 0
                            board[i][jj] *= 2
                            cnt += 1
                            break

                        elif board[i][jj] and board[i][j] != board[i][jj]:
                            cnt += 1
                            save = board[i][j]
                            board[i][j] = 0
                            board[i][jj + 1] = save
                            break

                        elif jj == cnt:
                            save = board[i][j]
                            board[i][j] = 0
                            board[i][jj] = save

    elif d == 2:
        for i in range(a):
            cnt = 0
            for j in range(a - 1, -1, -1):
                if board[j][i]:
                    for jj in range(j + 1, a - cnt):
                        if board[j][i] == board[jj][i]:
                            board[j][i] = 0
                            board[jj][i] *= 2
                            cnt += 1
                            break

                        elif board[jj][i] and board[j][i] != board[jj][i]:
                            cnt += 1
                            save = board[j][i]
                            board[j][i] = 0
                            board[jj-1][i] = save
                            break

                        elif jj == a - cnt - 1:
                            save = board[j][i]
                            board[j][i] = 0
                            board[jj][i] = save

    elif d == 3:
        for i in range(a):
            cnt = 0
            for j in range(a):
                if board[j][i]:
                    for jj in range(j - 1, -1 + cnt, -1):
                        if board[j][i] == board[jj][i]:
                            board[j][i] = 0
                            board[jj][i] *= 2
                            cnt += 1
                            break

                        elif board[jj][i] and board[j][i] != board[jj][i]:
                            cnt += 1
                            save = board[j][i]
                            board[j][i] = 0
                            board[jj + 1][i] = save
                            break

                        elif jj == cnt:
                            save = board[j][i]
                            board[j][i] = 0
                            board[jj][i] = save

def dfs(a, d, lst):
    global v
    lst1 = deepcopy(lst)
    move(n, d, lst1)

    if a == 5:
        for k in lst1:
            v = max(v, max(k))
        return

    for k in range(4):
        dfs(a+1, k, lst1)

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
v = 0

for ii in range(4):
    arr1 = deepcopy(arr)
    dfs(1, ii, arr1)

print(v)