[백준] 2048 (Easy)

문제

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

TC

• 4 ^ 5: 4방향에 대해서 5번 합치는 방향을 고려함
• (move 함수의 시간 복잡도) * 4 ^ 5

Idea

문제를 읽어보면 최대 5번 전체 블록들을 상/하/좌/우 방향으로 이동 시켜서 블록 하나의 숫자가 제일 큰 것을 찾으라고 한다.

최대 5번 밖에 움직일 수 없으므로, 모든 경우를 탐색해보는 Brute-Force 방식으로 진행해보았다.

백트래킹을 위해 DFS를 수행하는 과정에서 이전 상태로 돌아갈 수 있도록, 미리 board의 상태를 저장한 다음 재귀적으로 함수를 호출하면서 해당 함수가 모든 일을 끝마칠 때 다시 원상복구 시키는 방식으로 구현하였다.

이 문제는 백트래킹 자체가 어려운 것이 아니라, 구현 방법에서 세세한 생각을 요구한다.
문제를 잘 읽어보면, 한 번의 이동에서 합쳐진 숫자들은 다시 합쳐지지 않는다는 점과 똑같은 수가 3개가 있을 때 이동하려고 하는 쪽의 칸이 먼저 합쳐진다는 부분이 있다.
여기서 합쳐지는 순서 또한 중요한 요인이라는 것을 염두에 두고 구현을 해야 한다.

블록을 이동시킬 때 3가지를 생각해야 한다.

1. 진행 방향 상에 가장 가까운 블록이 없는 경우
2. 진행 방향 상에 가장 가까운 블록이 있고, 그 값이 다른 경우
3. 진행 방향 상에 가장 가까운 블록이 있고, 그 값이 같은 경우

CODE

from copy import deepcopy

def move(graph, dir):
    if dir == 0: # 오른쪽으로 이동하기
        for i in range(n):
            # 오른쪽으로 이동할 때 기준이 되는 위치
            top = n-1
            for j in range(n-2, -1, -1):
                # 해당 위치에 값이 있으면
                if graph[i][j]:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    # 기준이 되는 위치의 값과 옮기려는 값이 동일하다면
                    if graph[i][top] == temp:
                        graph[i][top] *= 2
                        # 옮겼으면 기준 위치 하나 왼쪽으로 앞당기기
                        top -= 1
                    # 기준이 되는 위치에 값이 없다면, 옮기려는 값을 그 자리에 저장
                    elif graph[i][top] == 0:
                        graph[i][top] = temp
                    # 기준이 되는 위치의 값과 옮기려는 값이 동일하지 않다면
                    # 기준 위치 하나 왼쪽으로 앞당기고 그 자리에 값 저장
                    else:
                        top -= 1
                        graph[i][top] = temp

    elif dir == 1: # 왼쪽으로 이동하기
        for i in range(n):
            # 왼쪽으로 이동할 때 기준이 되는 위치
            top = 0
            for j in range(1, n):
                # 해당 위치에 값이 있다면
                if graph[i][j]:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    # 기준이 되는 위치의 값과 옮기려는 값이 동일하다면
                    if graph[i][top] == temp:
                        graph[i][top] *= 2
                        # 옮겼으면 기준 위치 하나 오른쪽으로 밀기
                        top += 1
                    # 기준이 되는 위치에 값이 없다면, 옮기려는 값을 그 자리에 저장
                    elif graph[i][top] == 0:
                        graph[i][top] = temp
                    # 기준이 되는 위치의 값과 옮기려는 값이 동일하지 않다면
                    # 기준 위치 하나 오른쪽으로 밀고 그 자리에 값 저장
                    else:
                        top += 1
                        graph[i][top] = temp

    elif dir == 2: # 아래쪽으로 이동하기
        for j in range(n):
            # 아래쪽으로 이동할 때 기준이 되는 위치
            top = n-1
            for i in range(n-2, -1, -1):
                # 해당 위치에 값이 있다면
                if graph[i][j]:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    # 기준이 되는 위치의 값과 옮기려는 값이 동일하다면
                    if graph[top][j] == temp:
                        graph[top][j] *= 2
                        # 옮겼으면 기준 위치 하나 위로 올려주기
                        top -= 1
                    # 기준이 되는 위치에 값이 없다면, 옮기려는 값을 그 자리에 저장
                    elif graph[top][j] == 0:
                        graph[top][j] = temp
                    # 기준이 되는 위치의 값과 옮기려는 값이 동일하지 않다면
                    # 기준 위치 하나 위쪽으로 올리고 그 자리에 값 저장
                    else:
                        top -= 1
                        graph[top][j] = temp

    elif dir == 3: # 위쪽으로 이동하기
        for j in range(n):
            # 위쪽으로 이동할 때 기준이 되는 위치
            top = 0
            for i in range(1, n):
                # 해당 위치에 값이 있다면
                if graph[i][j]:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    # 기준이 되는 위치의 값과 옮기려는 값이 동일하다면
                    if graph[top][j] == temp:
                        graph[top][j] *= 2
                        # 옮겼으면 기준 위치 하나 아래로 내려주기
                        top += 1
                    # 기준이 되는 위치에 값이 없다면, 옮기려는 값을 그 자리에 저장
                    elif graph[top][j] == 0:
                        graph[top][j] = temp
                    # 기준이 되는 위치의 값과 옮기려는 값이 동일하지 않다면
                    # 기준 위치 하나 아래로 내리고 그 자리에 값 저장
                    else:
                        top += 1
                        graph[top][j] = temp

    return graph

# 보드의 크기
n = int(input())
# 보드의 초기 상태
graph = [list(map(int, input().split())) for _ in range(n)]

# 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값
result = 0
def dfs(graph, cnt):
    global result

    # 5번 이동했으면 가장 큰 값 구하기
    if cnt == 5:
        for i in range(n):
            for j in range(n):
                result = max(result, graph[i][j])
        return

    # 5번 이동 안했으면, 상하좌우 이동 진행하기
    for i in range(4):
        temp_graph = move(deepcopy(graph), i)
        dfs(temp_graph, cnt + 1)

dfs(graph, 0)
print(result)

Self Code Review

deepcopy가 시간복잡도가 큰걸로 알고 있다.
기존 배열을 변경하면 안되기에 깊은 복사하는 과정이 필요하기는 하나,
시간 복잡도 측면에서 다른 방법으로 구현할 수는 없을지 더 생각해봐야겠다.
가령 슬라이싱 연산이라던지...