12100번: 2048 (Easy) / gold 2 / 백트래킹

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

12100번: 2048 (Easy)

'''
12100번: 2048 (Easy) / gold 2 / 백트래킹
'''
import sys
import copy

input = sys.stdin.readline

# 방향(상하좌우)에 따라 그래프 움직이는 함수
def move_graph(dir, graph):
    collision = set()
    # 좌
    if dir == 0:
        for y in range(1, N):
            for x in range(N):
                nx, ny = x, y
                # 붙이기(쏠림)
                while ny >= 1 and graph[nx][ny] >= 1 and graph[nx][ny-1] == 0:
                    graph[nx][ny-1], graph[nx][ny] = graph[nx][ny],0
                    nx, ny = nx, ny-1
                # 합치기
                if ny >= 1:
                    if graph[nx][ny] >= 1 and graph[nx][ny-1] == graph[nx][ny]:
                        if (nx, ny-1) not in collision:
                            graph[nx][ny-1] *= 2
                            graph[nx][ny] = 0
                            collision.add((nx, ny-1))
    # 우
    elif dir == 1:
        for y in range(N-2, -1,-1):
            for x in range(N):
                nx, ny = x, y
                # 붙이기(쏠림)
                while ny <= N-2 and graph[nx][ny] >= 1 and graph[nx][ny+1] == 0:
                    graph[nx][ny+1], graph[nx][ny] = graph[nx][ny],0
                    nx, ny = nx, ny+1
                # 합치기
                if ny <= N-2:
                    if graph[nx][ny] >= 1 and graph[nx][ny+1] == graph[nx][ny]:
                        if (nx, ny+1) not in collision:
                            graph[nx][ny+1] *= 2
                            graph[nx][ny] = 0
                            collision.add((nx, ny+1))
    # 상
    elif dir == 2:
        for x in range(1, N):
            for y in range(N):
                nx, ny = x, y
                # 붙이기(쏠림)
                while nx >= 1 and graph[nx][ny] >= 1 and graph[nx-1][ny] == 0:
                    graph[nx-1][ny], graph[nx][ny] = graph[nx][ny],0
                    nx, ny = nx-1, ny
                # 합치기
                if nx >= 1:
                    if graph[nx][ny] >= 1 and graph[nx-1][ny] == graph[nx][ny]:
                        if (nx-1, ny) not in collision:
                            graph[nx-1][ny] *= 2
                            graph[nx][ny] = 0
                            collision.add((nx-1, ny))
    # 하 
    else:
        for x in range(N-2, -1, -1):
            for y in range(N):
                nx, ny = x, y
                # 붙이기(쏠림)
                while nx <= N-2 and graph[nx][ny] >= 1 and graph[nx+1][ny] == 0:
                    graph[nx+1][ny], graph[nx][ny] = graph[nx][ny],0
                    nx, ny = nx+1, ny
                # 합치기
                if nx <= N-2:
                    if graph[nx][ny] >= 1 and graph[nx+1][ny] == graph[nx][ny]:
                        if (nx+1, ny) not in collision:
                            graph[nx+1][ny] *= 2
                            graph[nx][ny] = 0
                            collision.add((nx+1, ny))

# 그래프 백트래킹 함수 
def backtracking(depth, graph):
    global res
    if depth == 5:
        max_num = 0
        for line in graph:
            if max_num < max(line):
                max_num = max(line)
        res.append(max_num)
        return
    for dir in range(4):
        copy_graph = copy.deepcopy(graph)
        move_graph(dir, copy_graph)
        backtracking(depth + 1, copy_graph)

# 입력받기
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
# 백트래킹 실행하기
res = []
backtracking(0,graph)
print(max(res))

코드 리뷰

- 해당 문제를 푸는데 약 60분 소요되었고, 정답 판정을 받았습니다.

- 백트래킹 알고리즘 문제를 선택해서 푼 문제이기에 어떻게 접근 할지 알고 문제를 접근했습니다.