[백준] 12100 2048 (Easy) (Python 파이썬)

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

12100번: 2048 (Easy)

문제 설명

문제에서 주어진 2048 게임을 구현하는 문제이다.

평소의 2048 게임과는 다르게 이동시 새 블록이 추가되지는 않으며

5번 움직였을 때 맵 내의 최대값을 출력하면 된다.

---

풀이 과정

백트래킹을 이용해 모든 경우의 수에 대해 확인을 해야 하는 브루트포스 문제이다.

 

움직일 수 있는 방향은 동, 서, 남, 북 4가지 이다.

만약, 동쪽으로 움직인다면 모든 행에 대해 n - 1칸부터 0번째 칸까지 동쪽으로 움직이는 것을 구현한다.

 

현재 움직이려는 블록의 동쪽 마지노선의 블록이 현재 블록과 같은 수라면

수를 더해준 후 마지노선 칸에 그 수를 넣어주고

현재 블록은 0으로 만들어 다음 블록들이 이동할 수 있도록 만든다.

( 0 0 2 2 = > 0 0 0 4 )

 

마지노선 블록이 0이라면 그 칸을 현재 블록의 숫자로 대체한 후

현재 블록을 0으로 만든다.

 

마지노선이 현재 블록과 같은 수가 아니라면, 합칠 수가 없기 때문에 마지노선을 하나 당긴다.

 

여기서 말하는 마지노선이란, 처음에는 동쪽 가장 끝이 될 것이며

동쪽 가장 끝이 이미 계산이 된 상태라면 -1씩 해주어 마지노선을 하나씩 줄여주는 것을 말한다.

 

그리고, 동쪽으로 움직인 경우를 만든 후에

서쪽으로 움직일 때는 동쪽으로 움직인 게임판을 이어서 이용하는 것이 아니라

동쪽으로 움직이기 전의 게임판을 서쪽으로 움직여야 하기 때문에

깊은복사(DeepCopy)를 통해 기존 맵을 복사해둔 후에 그 맵을 이동하도록 한다.

 

이를 코드로 구현하면 다음과 같다.

from copy import deepcopy

n = int(input())

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

def move(board, dir):
    if dir == 0:  # 동쪽
        for i in range(n):
            top = 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][top] == 0:
                        board[i][top] = tmp
                    elif board[i][top] == tmp:
                        board[i][top] = tmp * 2
                        top -= 1
                    else:
                        top -= 1
                        board[i][top] = tmp

    elif dir == 1:  # 서쪽
        for i in range(n):
            top = 0
            for j in range(1, n):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][top] == 0:
                        board[i][top] = tmp
                    elif board[i][top] == tmp:
                        board[i][top] = tmp * 2
                        top += 1
                    else:
                        top += 1
                        board[i][top] = tmp

    elif dir == 2:  # 남쪽
        for j in range(n):
            top = n - 1
            for i in range(n - 2, -1, -1):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[top][j] == 0:
                        board[top][j] = tmp
                    elif board[top][j] == tmp:
                        board[top][j] = tmp * 2
                        top -= 1
                    else:
                        top -= 1
                        board[top][j] = tmp

    else:
        for j in range(n):
            top = 0
            for i in range(1, n):
                if board[i][j]:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[top][j] == 0:
                        board[top][j] = tmp
                    elif board[top][j] == tmp:
                        board[top][j] = tmp * 2
                        top += 1
                    else:
                        top += 1
                        board[top][j] = 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)

ans = 0
dfs(graph, 0)
print(ans)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !