20210129_코테공부

# 12100 2048(Easy) (골드2)

• 어렵... 또 풀어보자...ㅠ
• 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
• 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
• 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

from copy import deepcopy

N = int(input())
Board = [list(map(int, input().split())) for i in range(N)] # n*n 보드 입력받기

def rotate90(B, N): #판 90도 회전시키기(암기할것)
    NB = deepcopy(B) # 배열 복사하기 NB = B 하면 주소값만 복사됨
    for i in range(N):
        for j in range(N):
            NB[j][N-i-1] = B[i][j] # 90도 돌리기
    return NB

def convert(lst, N): # 슬라이드 했을 때 결과물
    new_list = [i for i in lst if i]
    for i in range(1, len(new_list)):
        if new_list[i-1] == new_list[i]: #같은수이면
            new_list[i-1] *= 2 # 합치고
            new_list[i] = 0 # 나머지 제거
    new_list = [i for i in new_list if i]
    return new_list + [0] * (N-len(new_list))

def dfs(N, B, count):
    ret = max([max(i) for i in B]) #보드의 최대값
    if count == 0: # 5번 다 돌았을 때 최대값 출력
        return ret
    for _ in range(4): # 상하좌우 이동 경우의 수
        X = [convert(i, N) for i in B] # 슬라이드
        if X != B:
            ret = max(ret, dfs(N, X, count-1))
        B = rotate90(B, N) # 회전
    return  ret

print(dfs(N, Board, 5))