[2048(Easy)/G1/Python3]

12100번 2048 (Easy) G1

 

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

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

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

구현, 브루트포스 알고리즘, 시뮬레이션, 백트래킹

 

copy에 있는 깊은 복사를 사용하였다.

deque를 통해 합치는 연산을 구현하였으며, 합치는 방향과 인덱스는 get_move 함수로 제공받아 사용하였다.

백트래킹을 위해 한 번 연산이 끝나면 되돌리는 방식을 사용하였다.

 

import sys
import copy
from collections import deque

n = int(sys.stdin.readline())

game_map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

result = 0

def find(vec, time):
    global game_map
    if time == 6:
        global result
        v = max(game_map[0])
        for i in range(1, n):
            v = max(v, max(game_map[i]))
        result = max(result, v)
        return

    
    for i in range(1, 5):
        temp = copy.deepcopy(game_map)
        move(vec)
        find(i, time+1)
        game_map = temp

# 1, 3 좌 우, 2, 4 상 하
def move(i):
    dq = deque()
    ss, se, add, inde = get_move(i)
    if i % 2 == 1:
        for i in range(n):
            for j in range(ss, se, add):
                if game_map[i][j] != 0: dq.append(game_map[i][j])
            recent_v, recent_index = 0, inde
            while dq:
                v = dq.popleft()
                if recent_v == v:
                    game_map[i][recent_index] = v+v
                    recent_v = 0
                    continue
                recent_index += add
                game_map[i][recent_index] = v
                recent_v = v
            for j in range(recent_index + add, se, add):
                game_map[i][j] = 0
    else:
        for j in range(n):
            for i in range(ss, se, add):
                if game_map[i][j] != 0: dq.append(game_map[i][j])
            recent_v, recent_index = 0, inde
            while dq:
                v = dq.popleft()
                if recent_v == v:
                    game_map[recent_index][j] = v+v
                    recent_v = 0
                    continue
                recent_index += add
                game_map[recent_index][j] = v
                recent_v = v
            for i in range(recent_index+add, se, add):
                game_map[i][j] = 0

# 1, 3 좌 우, 2, 4 상 하
def get_move(i):
    if i <= 2:
        return [0, n, 1, -1]
    return [n-1, -1, -1, n]

for i in range(1, 5):
    temp = copy.deepcopy(game_map)
    find(i, 1)
    game_map = temp

print(result)​

 

---