[백준 12100번] 2048 (Easy) - python

문제 링크

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

12100번: 2048 (Easy)

 

풀이 

백트래킹 + 구현 문제

하나씩 내려가는 문제는 몇 번 풀어보았는데, 본 문제에서 중요한 것은 이미 합쳐진 블록은 또 다른 블록과 합쳐질 수 없다는 것이다. 

따라서 이미 합쳐진 블록부터는 해당 방향으로 이동하지 않도록 해야한다. 

기준 블록을 이동할 방향의 끝으로 잡고, 만약 합쳐졌거나 다른 블록이 있어 더이상 이동할 수 없다면 기준 블록을 하나씩 올려주는 것이다.

import copy

def up(graph):

    for j in range(n):
    	# 기준 블록 
        col = 0
        for i in range(1, n):

            if graph[i][j] :
                tmp = graph[i][j]
                graph[i][j] = 0
				
                # 빈칸이면 채워 넣음
                if graph[col][j] == 0:	
                    graph[col][j] = tmp
                # 합쳐질 수 있는 칸이면 합치고 기준 블록 증가 
                elif graph[col][j] == tmp :
                    graph[col][j] = tmp * 2
                    col += 1
               # 다른 블록이 있어 합쳐지거나 이동할 수 없으면 
                else :
                    col += 1
                    # 빈칸 위에 넣음
                    graph[col][j] = tmp

    return graph

def right(graph):

    for i in range(n):
        row = n-1
        for j in range(n-2, -1, -1):
            if graph[i][j] :
                tmp = graph[i][j]
                graph[i][j] =0

                if graph[i][row] == 0 :
                    graph[i][row] = tmp
                elif graph[i][row]== tmp:
                    graph[i][row] = tmp * 2
                    row -= 1
                else :
                    row -= 1
                    graph[i][row] = tmp
    return graph

def left(graph):

    for i in range(n):
        row = 0
        for j in range(1, n):
            if graph[i][j] :
                tmp = graph[i][j]
                graph[i][j] = 0

                if graph[i][row] == 0 :
                    graph[i][row] = tmp
                elif graph[i][row] == tmp :
                    graph[i][row ]= tmp * 2
                    row += 1
                else:
                    row += 1
                    graph[i][row] = tmp
    return graph

def down(graph):
    for j in range(n):
        col = n -1
        for i in range(n-2, -1, -1):
            if graph[i][j] :
                tmp = graph[i][j]
                graph[i][j] = 0

                if graph[col][j]==0:
                    graph[col][j] = tmp
                elif graph[col][j] == tmp:
                    graph[col][j] = tmp * 2
                    col -= 1
                else :
                    col -= 1
                    graph[col][j] = tmp
    return graph

def dfs(graph, cnt):
    global ans
    if cnt == 5 :
        tmp = 0
        for i in graph:
            tmp = max(tmp,max(i))
        ans = max(ans, tmp)
        return

    dfs(up(copy.deepcopy(graph)), cnt + 1)
    dfs(down(copy.deepcopy(graph)), cnt + 1)
    dfs(left(copy.deepcopy(graph)), cnt + 1)
    dfs(right(copy.deepcopy(graph)), cnt + 1)


n = int(input())

graph = []
ans = 0
for _ in range(n):
    graph.append(list(map(int,input().split())))

dfs(graph,0)
print(ans)