백준 12100 2048 (Easy) (파이썬)

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

12100번: 2048 (Easy)

1. dfs 중복순열로 회전 방향을 정한다. 회전할 때는 move 함수를 실행해서 바로 이동한다

   temp_a에는 회전하기 전의 보드 상태가 저장되있고 회전하지 않으면 temp_a를 불러와서 지도를 초기화한다

2. move 함수는 입력 받은 방향에 따라서 한번에 이동한다. dir = 0~3은 각각 상하좌우 방향을 의미한다

3. 위로 이동할 경우 이동할 맨 끝 idx를 0으로 설정한다

4. 블럭이 있으면 조건대로 구현한다

   a[idx][j]가 0이면 빈칸이기 이므로 옮기기만 한다. 나중에 합칠 수 있는지 확인해야 하기 때문에 idx는 변하지 않는다

   a[idx][j]가 같은 값이면 합쳐서 두배를 만들고, 한 번 합친 블럭은 더 합칠 수 없으므로 idx를 증가시킨다

   블럭이 있는데 다른 값이면 그 위에 쌓여야 하기 때문에 idx를 먼저 증가시키고 블럭을 옮긴다

   다른 방향도 위와 같이 구현하면 된다

5. 5번 이동했으면 최대값을 갱신한다

import sys, copy

input = sys.stdin.readline

def move(dir):
    if dir == 0:
        for j in range(n):
            idx = 0
            for i in range(1, n):
                if a[i][j]:
                    temp = a[i][j]
                    a[i][j] = 0
                    if a[idx][j] == 0:
                        a[idx][j] = temp
                    elif a[idx][j] == temp:
                        a[idx][j] = temp * 2
                        idx += 1
                    else:
                        idx += 1
                        a[idx][j] = temp

    elif dir == 1:
        for j in range(n):
            idx = n-1
            for i in range(n - 2, -1, -1):
                if a[i][j]:
                    temp = a[i][j]
                    a[i][j] = 0
                    if a[idx][j] == 0:
                        a[idx][j] = temp
                    elif a[idx][j] == temp:
                        a[idx][j] = temp * 2
                        idx -= 1
                    else:
                        idx -= 1
                        a[idx][j] = temp

    elif dir == 2:
        for i in range(n):
            idx = 0
            for j in range(1, n):
                if a[i][j]:
                    temp = a[i][j]
                    a[i][j] = 0
                    if a[i][idx] == 0:
                        a[i][idx] = temp
                    elif a[i][idx] == temp:
                        a[i][idx] = temp * 2
                        idx += 1
                    else:
                        idx += 1
                        a[i][idx] = temp

    else:
        for i in range(n):
            idx = n-1
            for j in range(n - 2, -1, -1):
                if a[i][j]:
                    temp = a[i][j]
                    a[i][j] = 0
                    if a[i][idx] == 0:
                        a[i][idx] = temp
                    elif a[i][idx] == temp:
                        a[i][idx] = temp * 2
                        idx -= 1
                    else:
                        idx -= 1
                        a[i][idx] = temp


def dfs(cnt):
    global a, ans
    if cnt == 5:
        for i in range(n):
            for j in range(n):
                ans = max(ans, a[i][j])
        return

    temp_a = copy.deepcopy(a)
    for i in range(4):
        move(i)
        dfs(cnt + 1)
        a = copy.deepcopy(temp_a)


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