[백준] 12100번 : 2048 (Easy)

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

12100번: 2048 (Easy)

해당 문제는 5번의 이동으로 테이블에 있는 값중 최대값을 찾아서 리턴해야하는 문제이다.

순열 조합으로 해당 문제를 해결해야한다. R->R->R->L->R 의 결과와 R->L->R->R->R 의 결과가 다르기 때문이다.

순열의 조건으로 탐색을 시작하고 5번의 탐색의 깊이를 백트래킹 조건으로 놓는다. 즉 모든 경우의 수를 탐색하여 최대값을 리턴 하면 된다.

 

움직이는 조건은 Up,Down,Right,Left로 움직일 수 있다 따라서 상,하,좌,우 로 움직이는 함수를 정의한다.

 

 

import copy
N = int(input())
table = []
for _ in range(N):
    table.append(list(map(int, input().split())))


def up(table):
    for j in range(N):
        pointer = 0
        for i in range(1, N):
            if table[i][j]:
                temp = table[i][j]
                table[i][j] = 0
                
                if table[pointer][j]:
                    if table[pointer][j] == temp: # 포인터와 같다면
                        table[pointer][j] = temp*2
                        pointer += 1
                    else:
                        pointer += 1
                        table[pointer][j] = temp
                        
                else:
                    table[pointer][j] = temp
                
    return table
                    
def down(table):
    for j in range(N):
        pointer = N-1
        for i in range(N-2, -1, -1):
            if table[i][j]:
                temp = table[i][j]
                table[i][j] = 0
                if table[pointer][j]:
                    if table[pointer][j] == temp: # 포인터와 같다면
                        table[pointer][j] = temp*2
                        pointer -= 1
                    else:
                        pointer -= 1
                        table[pointer][j] = temp
                        
                else:
                    table[pointer][j] = temp
                
    return table
                    
def left(table):
    for i in range(N):
        pointer = 0
        for j in range(1, N):
            if table[i][j]:
                temp = table[i][j]
                table[i][j] = 0
                if table[i][pointer]:
                    if table[i][pointer] == temp: # 포인터와 같다면
                        table[i][pointer] = temp*2
                        pointer += 1
                    else:
                        pointer += 1
                        table[i][pointer] = temp
                        
                else:
                    table[i][pointer] = temp
                
    return table
                
def right(table):
    for i in range(N):
        pointer = N-1
        for j in range(N-2, -1, -1):
            if table[i][j]:
                temp = table[i][j]
                table[i][j] = 0
                if table[i][pointer]:
                    if table[i][pointer] == temp: # 포인터와 같다면
                        table[i][pointer] = temp*2
                        pointer -= 1
                    else:
                        pointer -= 1
                        table[i][pointer] = temp
                        
                else:
                    table[i][pointer] = temp
                
    return table
                
def move(pos, table):
    if pos == 0:
        return up(table)
    elif pos == 1:
        return down(table)
    elif pos == 2:
        return left(table)
    else :
        return right(table)

def dfs(table, depth):
    if depth == 5:
        return max(map(max, table))
    
    maxvalue = 0
    for i in range(4):
        maxvalue = max(maxvalue, dfs(move(i, copy.deepcopy(table)), depth+1))
    
    return maxvalue

print(dfs(table, 0))