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

풀이

모든 경우의 수에 대해서 검사를 해봐야 어떤 경우에 가장 큰 수가 만들어지는지 알 수 있는 문제입니다.

그래서, 풀이 방법은 ‘백트래킹’을 이용하여 모든 경우의 수를 검사하는 것입니다.

 

백트래킹 자체의 구현은 어렵지 않지만 각 수들을 move 하는 것에 시간이 좀 걸렸던 문제였습니다.

위, 아래 이동은 row를 이동하면서 갱신해야하고

왼쪽, 오른쪽 이동은 column을 이동하면서 갱신해야합니다.

 

각 칸에 대하여 선택된 칸 뒤에 남아있는 칸을 순서대로 검사하면서 남아있는 칸이 0이면 넘어가고, 0이 아니면 선택된 칸(0이 아니면)과 합치거나 혹은 선택된 칸(0이면)에 그 칸의 값을 이동시켰습니다.

 

선택된 칸과 남아있는 칸이 합쳐졌다면 다음 칸으로 넘어가서 같은 과정을 반복하면 되지만, 만약 선택된 칸이 0이면 남아있는 칸 뒤에 또 같은 값을 가진 칸이 있을 수 있기 때문에 멈추지 않고 검사해주어야 합니다.

 

대충 표로 보이면 다음과 같습니다.

 

1. 선택된 칸이 0 인 경우

0

2

2

선택된 칸이 0이기 때문에 뒤에 남아있는 칸 2가 0으로 이동합니다.

2

0

2

그 후, 이동하였다해도 뒤에 있는 칸에 의해 합쳐질 수 있기 때문에 멈추지 않고 다음 칸을 검사합니다.

이때, 같은 값이기 때문에 빨간색 칸에 파란색 값을 합쳐줍니다.

4

0

0

각 칸마다 합치는 횟수는 1번밖에 안주어지므로 다음 칸을 선택하여 같은 과정을 반복합니다.

1. 선택된 칸이 숫자인 경우

2

2

4

선택된 칸과 뒤에 남아있는 칸이 같은 값이라 합칩니다.

4

0

4

이미 선택된 값이 합쳐졌기 때문에 더 이상 합쳐지지 못하기 때문에 다음 칸을 선택합니다.

그 후, 1번 과정에 따라 파란색 값인 4가 0으로 이동하고 끝납니다.

4

4

0

한 마디로 그냥 각 칸을 갱신하면서 이동하고자 하는 방향으로 이동시키는 것입니다.

 

그림보다 코드가 더 잘 이해될 거 같네용.

코드로 보이면 다음과 같습니다…

 

코드

import sys
input = sys.stdin.readline

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

def board_move(wasd):
    if (wasd == 0): # 위
        for column in range(N):
            for row in range(N-1):
                for new_row in range(row+1, N):
                    if (board[row][column] != 0 and board[new_row][column] != 0):
                        if (board[row][column] == board[new_row][column]):
                            board[row][column] += board[new_row][column]
                            board[new_row][column] = 0
                            break
                        else:
                            break
                    elif (board[row][column] == 0 and board[new_row][column] != 0):
                        board[row][column] = board[new_row][column]
                        board[new_row][column] = 0
    elif (wasd == 1): # 아래
        for column in range(N):
            for row in range(N-1, 0, -1):
                for new_row in range(row-1, -1, -1):
                    if (board[row][column] != 0 and board[new_row][column] != 0):
                        if (board[row][column] == board[new_row][column]):
                            board[row][column] += board[new_row][column]
                            board[new_row][column] = 0
                            break
                        else:
                            break
                    elif (board[row][column] == 0 and board[new_row][column] != 0):
                        board[row][column] = board[new_row][column]
                        board[new_row][column] = 0
    elif (wasd == 2): # 왼쪽
        for row in range(N):
            for column in range(N-1):
                for new_column in range(column+1, N):
                    if (board[row][column] != 0 and board[row][new_column] != 0):
                        if (board[row][column] == board[row][new_column]):
                            board[row][column] += board[row][new_column]
                            board[row][new_column] = 0
                            break
                        else:
                            break
                    elif (board[row][column] == 0 and board[row][new_column] != 0):
                        board[row][column] = board[row][new_column]
                        board[row][new_column] = 0
    elif (wasd == 3):
        for row in range(N):
            for column in range(N-1, 0, -1):
                for new_column in range(column-1, -1, -1):
                    if (board[row][column] != 0 and board[row][new_column] != 0):
                        if (board[row][column] == board[row][new_column]):
                            board[row][column] += board[row][new_column]
                            board[row][new_column] = 0
                            break
                        else:
                            break
                    elif (board[row][column] == 0 and board[row][new_column] != 0):
                        board[row][column] = board[row][new_column]
                        board[row][new_column] = 0

def n_2048(deep):
    global mNum, board
    if (deep == 5):
        for i in range(N):
            mNum = max(mNum, max(board[i]))
        return
    
    bd = [b[:] for b in board]
    for i in range(4):
        board_move(i)
        n_2048(deep + 1)
        board = [b[:] for b in bd]

n_2048(0)
print(mNum)