백준 2048 (Easy) [12100] Python 코드 + 해설

문제 이해하기

2048 게임은 4×4 크기의 보드에서 숫자 블록을 이동시키며 즐기는 게임이다. 하지만 이번 문제에서는 보드의 크기가 N×N (1 ≤ N ≤ 20)으로 주어지고, 최대 5번의 이동으로 만들 수 있는 가장 큰 블록의 값을 찾아야 한다.

게임 규칙 정리

• 상하좌우 네 방향으로 보드의 모든 블록을 한꺼번에 이동시킬 수 있다.
• 같은 숫자를 가진 두 블록이 충돌하면 하나로 합쳐진다.
• 한 번의 이동에서 이미 합쳐진 블록은 다시 합쳐질 수 없다.
• 최대 5번 이동하여 가장 큰 블록의 값을 구해야 한다.

해결 방법: DFS로 모든 경우의 수 탐색하기

이 문제는 모든 가능한 이동 조합을 시도해보는 방법으로 해결할 수 있다. 최대 이동 횟수가 5번이므로, 가능한 이동의 수는 4^5 = 1024가지이다. 따라서 DFS(깊이 우선 탐색)을 사용하여 모든 경우를 탐색해도 충분하다.

DFS란?

DFS는 한 방향으로 갈 수 있을 때까지 깊게 들어가고, 더 이상 갈 곳이 없으면 이전 노드로 돌아오는 방식이다. 이 문제에서는 이동 횟수를 깊이로 생각하고, 각 이동마다 네 방향으로 분기하여 최대 깊이 5까지 탐색한다.

bfs and dfs

구현 단계

1. 입력 받기
   • 보드의 크기 N과 초기 상태를 입력받는다.
2. 블록 이동 함수 구현
   • 보드를 특정 방향으로 이동시키는 함수를 만든다.
   • 이동 시 블록의 합쳐짐과 이미 합쳐진 블록은 다시 합쳐지지 않음을 처리해야 한다.
3. DFS 함수 구현
   • 현재 보드 상태와 이동 횟수를 인자로 받는다.
   • 이동 횟수가 5보다 크면 종료한다.
   • 네 방향으로 이동시킨 새로운 보드 상태로 DFS를 재귀 호출한다.
   • 각 단계에서 가장 큰 블록의 값을 갱신한다.
4. 최대 값 갱신
   • 모든 DFS 탐색이 끝나면 최대 값을 출력한다.

 

최종 코드는 아래와 같다.

import sys
import copy
sys.setrecursionlimit(100000)

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
max_block = 0

def move(board, direction):
    N = len(board)
    new_board = [[0]*N for _ in range(N)]
    merged = [[False]*N for _ in range(N)]

    if direction == 0:  # 위로 이동
        for j in range(N):
            index = 0
            for i in range(N):
                if board[i][j]:
                    temp = board[i][j]
                    board[i][j] = 0
                    if new_board[index][j] == 0:
                        new_board[index][j] = temp
                    elif new_board[index][j] == temp and not merged[index][j]:
                        new_board[index][j] *= 2
                        merged[index][j] = True
                        index += 1
                    else:
                        index += 1
                        new_board[index][j] = temp
    elif direction == 1:  # 아래로 이동
        for j in range(N):
            index = N - 1
            for i in range(N-1, -1, -1):
                if board[i][j]:
                    temp = board[i][j]
                    board[i][j] = 0
                    if new_board[index][j] == 0:
                        new_board[index][j] = temp
                    elif new_board[index][j] == temp and not merged[index][j]:
                        new_board[index][j] *= 2
                        merged[index][j] = True
                        index -= 1
                    else:
                        index -= 1
                        new_board[index][j] = temp
    elif direction == 2:  # 왼쪽으로 이동
        for i in range(N):
            index = 0
            for j in range(N):
                if board[i][j]:
                    temp = board[i][j]
                    board[i][j] = 0
                    if new_board[i][index] == 0:
                        new_board[i][index] = temp
                    elif new_board[i][index] == temp and not merged[i][index]:
                        new_board[i][index] *= 2
                        merged[i][index] = True
                        index += 1
                    else:
                        index += 1
                        new_board[i][index] = temp
    else:  # 오른쪽으로 이동
        for i in range(N):
            index = N - 1
            for j in range(N-1, -1, -1):
                if board[i][j]:
                    temp = board[i][j]
                    board[i][j] = 0
                    if new_board[i][index] == 0:
                        new_board[i][index] = temp
                    elif new_board[i][index] == temp and not merged[i][index]:
                        new_board[i][index] *= 2
                        merged[i][index] = True
                        index -= 1
                    else:
                        index -= 1
                        new_board[i][index] = temp
    return new_board

def dfs(board, depth):
    global max_block
    if depth == 5:
        for i in range(N):
            max_block = max(max_block, max(board[i]))
        return
    for i in range(4):
        new_board = move(copy.deepcopy(board), i)
        dfs(new_board, depth + 1)

dfs(board, 0)
print(max_block)

12100 정답

도움이 되셨다면 공감 및 댓글 부탁드립니다.