[Gold I] 2048 (Easy) - 12100

문제 링크

성능 요약

메모리: 35508 KB, 시간: 116 ms

분류

백트래킹, 브루트포스 알고리즘, 구현, 시뮬레이션

문제 설명

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 2048를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

---

문제 풀이

문제 분석

2048 게임 보드가 주어졌을 때, 최대 5번의 이동(상, 하, 좌, 우)을 통해 만들 수 있는 가장 큰 블록의 값을 구하는 문제입니다. 이동 시 같은 값을 가진 블록이 충돌하면 합쳐지고, 한 번의 이동에서 이미 합쳐진 블록은 다시 합쳐질 수 없습니다.

접근 방법

문제에서 이동 횟수가 최대 5번으로 제한되어 있으므로, 모든 가능한 이동 조합을 시도하는 완전 탐색(브루트 포스) 방식을 사용합니다. 각 이동 방향에 따라 보드를 이동시키고, 이동 결과를 바탕으로 재귀적으로 탐색을 진행합니다. DFS(Depth-First Search)를 사용하여 5번의 이동을 수행한 후, 보드 내의 최댓값을 갱신합니다.

구현 설명

1. DFS 함수 구현

DFS 함수는 현재 보드 상태, 이동 횟수, 그리고 최대 블록 값을 저장하는 리스트를 입력으로 받습니다. 이동 횟수가 5가 되면 현재 보드의 최댓값을 answer 리스트에 추가하고 종료합니다.

2. 보드 이동 함수 구현 (좌, 우, 상, 하)

• 각 이동 방향에 대해, 보드의 각 행 또는 열을 순회하면서 0이 아닌 블록들을 추출합니다.
• 추출된 블록들을 순서대로 처리하면서, 이전 블록과 현재 블록의 값이 같은 경우 두 블록을 합칩니다. 합쳐진 블록은 다음 블록과 다시 합쳐질 수 없도록 prev 변수를 사용하여 제어합니다.
• 합쳐진 블록 또는 남아있는 블록들을 새로운 보드에 순서대로 채워 넣습니다. 빈 칸은 0으로 채워집니다.

3. 이동 후 상태 비교

각 방향으로 이동시킨 후의 보드 상태가 이동 전과 같다면, 해당 방향으로의 탐색은 의미가 없으므로 가지치기를 합니다. 이를 통해 불필요한 탐색을 줄입니다.

4. 최대 블록 값 갱신

DFS 탐색이 종료되면, answer 리스트에 저장된 각 경우의 최댓값 중 가장 큰 값을 찾아 최종 결과를 출력합니다.

⏱복잡도 분석

• 시간 복잡도: 각 이동마다 4가지 방향이 있으므로, 최대 5번 이동하는 경우의 수는 4^5 = 1024입니다. 각 이동마다 O(N^2)의 시간이 걸리므로, 전체 시간 복잡도는 O(4^5 * N^2) = O(1024 * N^2)입니다. N <= 20이므로, 시간 복잡도는 대략 O(409600)입니다.
• 공간 복잡도: DFS 재귀 호출 스택의 깊이는 최대 5입니다. 각 재귀 호출마다 N x N 크기의 보드를 복사하므로, 공간 복잡도는 O(5 * N^2) = O(N^2)입니다. answer리스트는 최대 4^5 개의 원소를 가질 수 있지만, 이는 N^2에 비해 상대적으로 작으므로 무시할 수 있습니다.

핵심 포인트

1. 완전 탐색 (DFS): 이동 횟수가 제한적이므로 모든 가능한 이동 조합을 시도하는 완전 탐색이 효율적입니다.
2. 보드 이동 로직 구현: 각 방향으로 블록을 이동시키고, 같은 값을 가진 블록을 합치는 로직을 정확하게 구현하는 것이 중요합니다. 특히, 문제에서 주어진 합쳐진 블록은 다시 합쳐질 수 없다는 조건을 고려해야 합니다.
3. 가지치기: 이동 후 보드 상태가 변하지 않으면 더 이상 탐색하지 않도록 하여 불필요한 연산을 줄입니다.

풀이 코드

import heapq
import sys

def DFS(graph, cnt, answer):
    if cnt == 5:
        maxnum = max(max(i) for i in graph)
        answer.append(maxnum)
        return
    
    n = len(graph)
    check = [i[:] for i in graph]
    #LRUD
    # 일단 0 은 무시하고 와야되고 같은게 있으면 합쳐지면서 움직여야된다
    #L
    graph2 = [[0]*n for i in range(n)]
    for i in range(n):
        prev = -1
        result = []
        for j in range(n):
            if graph[i][j] == 0:
                continue

            if prev == graph[i][j]:
                result[-1] = 2*prev
                prev = -1

            else:
                result.append(graph[i][j])
                prev = graph[i][j]
        
        for j in range(len(result)):
            graph2[i][j] = result[j]

    if not check == graph2:
        DFS(graph2,cnt+1,answer)

    #R
    graph2 = [[0]*n for i in range(n)]
    for i in range(n):
        prev = -1
        result = []
        for j in range(n-1,-1,-1):
            if graph[i][j] == 0:
                continue

            if prev == graph[i][j]:
                result[-1] = 2*prev
                prev = -1

            else:
                result.append(graph[i][j])
                prev = graph[i][j]
        
        for j in range(len(result)):
            graph2[i][n-1-j] = result[j]

    if not check == graph2:
        DFS(graph2,cnt+1,answer)

    #U
    graph2 = [[0]*n for i in range(n)]
    for i in range(n):
        prev = -1
        result = []
        for j in range(n):
            if graph[j][i] == 0:
                continue

            if prev == graph[j][i]:
                result[-1] = 2*prev
                prev = -1

            else:
                result.append(graph[j][i])
                prev = graph[j][i]
        
        for j in range(len(result)):
            graph2[j][i] = result[j]

    if not check == graph2:
        DFS(graph2,cnt+1,answer)

    #D
    graph2 = [[0]*n for i in range(n)]
    for i in range(n):
        prev = -1
        result = []
        for j in range(n-1,-1,-1):
            if graph[j][i] == 0:
                continue

            if prev == graph[j][i]:
                result[-1] = 2*prev
                prev = -1

            else:
                result.append(graph[j][i])
                prev = graph[j][i]
        
        for j in range(len(result)):
            graph2[n-1-j][i] = result[j]

    if not check == graph2:
        DFS(graph2,cnt+1,answer)


n = int(sys.stdin.readline())

graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

if n == 1:
    print(graph[0][0])

else:
    answer = []
    DFS(graph,0,answer)
    print(max(answer))