[백준] 12100 - 2048(Easy) 🕹️ (Python) / 골드 2 / 브루트포스

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제

문제를 요약하자면, 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어집니다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어집니다. 0은 빈칸을 나타내며, 이외의 값은 모두 블록을 나타냅니다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱 꼴입니다. 블록은 적어도 하나 주어집니다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력해야 합니다.

 

1) 예제 입출력❄️

예제 입출력

상, 하, 좌, 우로 움직일 때 판의 모든 블록들이 함께 움직입니다. 이 때 5번 이동시켜 얻을 수 있는 가장 큰 블록을 출력해야 합니다. 위의 예시에선 5번 어떻게 움직여도 맨 아랫줄 8이 2개 합쳐서 16이 되는 경우가 최대입니다.

 

2. 핵심 논리☢️

dfs를 통해 5번 움직이는 모든 경우의수를 탐색합니다. 아래 그림처럼 상, 하, 좌, 우로 움직이는 경우를 5번 깊이 까지 DFS로 탐색하는 것입니다.

핵심 논리

3. 풀이 코드✅

import sys
from copy import deepcopy
input=sys.stdin.readline

def move(board, dir):
    if dir == 0: # 위
        for j in range(N):
            pointer = 0
            for i in range(1, N):
                if board[i][j]:
                    tmp = board[i][j] # 현재 보드의 값
                    board[i][j] = 0
                    if board[pointer][j] == 0: # 포인터가 가리키는 수가 0일 때
                        board[pointer][j] = tmp
                    elif board[pointer][j] == tmp: # 포인터가 가리키는 수와 현재 위치의 수가 같을 때
                        board[pointer][j] *= 2
                        pointer += 1
                    else: # 포인터가 가리키는 수와 현재 위치의 수가 다를 때
                        pointer += 1
                        board[pointer][j] = tmp
    elif dir == 1: # 아래
        for j in range(N):
            pointer = N-1
            for i in range(N-2,-1,-1): # n-1, n-2, ..., 1, 0
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[pointer][j] == 0:
                        board[pointer][j] = tmp
                    elif board[pointer][j] == tmp:
                        board[pointer][j] = tmp*2
                        pointer -= 1
                    else:
                        pointer -= 1
                        board[pointer][j] = tmp
    elif dir == 2: # 오른쪽
        for i in range(N):
            pointer = N-1
            for j in range(N-2,-1,-1):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j]=0
                    if board[i][pointer] == 0:
                        board[i][pointer] = tmp
                    elif board[i][pointer] == tmp:
                        board[i][pointer] = tmp*2
                        pointer -= 1
                    else:
                        pointer -= 1
                        board[i][pointer] = tmp
    else: # 왼쪽
        for i in range(N):
            pointer = 0
            for j in range(1,N):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][pointer] == 0:
                        board[i][pointer] = tmp
                    elif board[i][pointer] == tmp:
                        board[i][pointer] = tmp*2
                        pointer += 1
                    else:
                        pointer += 1
                        board[i][pointer] = tmp
    return board

def dfs(board, cnt):
    global ans
    if cnt==5:
        for i in range(N):
            for j in range(N):
                ans = max(ans,board[i][j])
        return
    for i in range(4): # 상,하,좌,우
        tmp_board = move(deepcopy(board), i)
        dfs(tmp_board, cnt+1)

N = int(input())
graph = [list(map(int,input().split())) for _ in range(N)]
ans=0
dfs(graph, 0)
print(ans)

보드의 크기(N)을 입력받고, 게임판 초기 상태를 graph에 이중 리스트로 입력받습니다. 최종 출력할 값을 ans에 0으로 초기화 시켜주고 dfs(graph, 0)을 실행합니다. dfs함수는 ans를 전역 변수화 하고, 5번 움직인 경우 보드내부를 모두 탐색하며 최댓값을 ans에 저장하고 리턴하여 dfs함수가 끝납니다. 그러고 ans를 출력하면 정답입니다. dfs함수에서 5번 움직이지 않은 경우는 상, 하, 좌, 우를 move함수를 통해 탐색하여 보드를 갱신시킨 뒤 dfs를 재귀적으로 호출합니다.

 move함수는 보드를 deepcopy 해서 입력받은 후, 상, 하, 좌, 우로 한 번 움직이는 경우 보드가 어떻게 될지를 반영하여 보드 자체를 반환합니다. deepcopy를 하는 이유는 보드가 Call By Reference로 호출되기 때문에 board의 원본은 그대로 유지하기 위함입니다. 

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/12100_2048(Easy).ipynb 

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/