[백준/BOJ] #12100 2048 (Easy).python(파이썬)

전혀 Easy하지 않은 2048 (Easy)문제다ㅋㅋ

문제 링크 / 출처

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

12100번: 2048 (Easy)

 

문제 요약

잘 알려진 2048게임을 구현하고, 5번의 움직임을 수행했을 때 만들 수 있는 최댓값을 구하는 문제

[제약사항]

• 1 ≤ N ≤ 20
• 블록은 적어도 하나 주어진다.

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

 

풀이

이 게임은 상하좌우 네방향으로 움직임이 가능한데 최대 5번까지 이동할 수 있으므로 4**5 == 1024가지의 움직임이 가능하다.

 

네가지방향을 각각 구현하여 더 빨리 풀 수 있엇지만 코드를 최대한 짧게 줄이고자 여러 수식을 활용해 최대한 줄여보았다.

 

게임의 구현은 스택을 활용해 구현했다.

 

1. 이동할 방향과 같은 방향으로 배열을 탐색하며, 0이 아닌 값을 스택에 넣는다.
2. 스택에 넣음과 동시에 배열의 값을 0으로 변경해준다.
3. 스택에서 값을 num변수에 넣어 가져온뒤, 스택의 가장 위 값과 같은지 비교한다.
4. 같다면 두 수가 합쳐져야하므로 num변수로 합쳐준다.
5. 이번에는 이동할 방향의 반대방향으로 배열을 이동하면서 3~4를 반복해 num의 값을 넣어준다.

 

모든 경우의 수를 탐색하기 위해 비트연산을 이용했다. 모든 가능한 경우 각각에 대하여 이동리스트를 만들어 최대값을 구했다.

 

이 방법 보다는 재귀함수를 활용한 백트레킹 방식이 조금 더 시간을 아끼고 깔끔하게 작성할 수 있었을 것 같다.

 

코드

# 2048 (Easy)

def push(direction):
    x, y = direction

    a = int((N - 1) / 2 + (x + y) * (1 - N) / 2)
    b = int((N - 1) / 2 + (x + y) * (N + 1) / 2)
    s = x + y

    # 4방향 함수로
    for rc in range(a, b, s):
        temp = []
        for cr in range(a, b, s):
            rorc = rc * abs(y) + cr * abs(x)
            corr = cr * abs(y) + rc * abs(x)
            if board_copy[rorc][corr]:
                temp.append(board_copy[rorc][corr])
                board_copy[rorc][corr] = 0

        c_i = int((N - 1) / 2 + (x + y) * (N - 1) / 2)

        while temp:
            num = temp.pop()
            if len(temp) > 0 and num == temp[-1]:
                num += temp.pop()
            board_copy[rc * abs(y) + c_i * abs(x)][c_i * abs(y) + rc * abs(x)] = num
            c_i -= x + y


N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
max_num = 0
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

for i in range(1 << 10):  # 5번 반복 완전탐색
    cmd_list = []
    for j in range(0, 10, 2):
        if i & (1 << j) and i & (1 << (j + 1)):
            cmd_list.append(directions[0])
        elif i & (1 << j):
            cmd_list.append(directions[1])
        elif i & (1 << (j + 1)):
            cmd_list.append(directions[2])
        else:
            cmd_list.append(directions[3])

    board_copy = [board[i][:] for i in range(N)]
    for cmd in cmd_list:  # 모든 경우에 대해 반복
        push(cmd)
    now_max_num = max(map(max, board_copy))
    if max_num < now_max_num:
        max_num = now_max_num

print(max_num)