[Python] 백준 12100번 : 2048 (Easy)

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

12100번: 2048 (Easy)

---

💡 문제 풀이

백트래킹 문제이다. 백트래킹 자체를 구현하는 것은 하나도 어렵지 않다.

5번까지 이동 가능하므로 5번 이동했을 때 (= cnt가 5일 때) 최대 크기의 블록을 찾아서 최신화만 해주면 된다.

이 문제가 어려운 점은 이동이다.

 

이동에서 주의할 점이 2가지가 있다.

1. 앞의 모든 칸이 비어있다면 끝까지 이동한다는 점

2. 합치는 것은 연속적으로 일어나지 않아 한번 합쳐진 것은 또 합쳐질 수 없다는 점

 

이 2가지 이유 때문에 그냥 반복문을 돌려버리면 시간 초과가 나고 연속적으로 숫자가 합쳐지는 문제가 생긴다.

한계점을 만들면 이 문제들을 해결할 수 있다. (한계점 = 값을 넣을 수 있는 곳)

이동할 때 발생하는 경우는 빈칸일 때, 같은 값일 때, 둘 다 아닐 때 이렇게 3가지이다.

따라서, 빈칸인 경우 확인하는 값을 한계점까지 당겨준다.

같은 값인 경우 해당 값을 2배 해주고 또 합쳐질 수 없으니 다음 지점을 한계점으로 설정한다.

아무것도 할 수 없는 경우 한계점을 다음으로 설정하고 그 위치로 값을 이동시켜준다.

 

이해를 위해서, 0 2 2 0 2 를 왼쪽(←)으로 이동시킨다면 다음과 같은 절차대로 이동한다.

 step 0 : 0 2 2 0 2 / end = 0

 step 1 : 2 0 2 0 2 / end = 0

 step 2 : 4 0 0 0 2 / end = 1

 step 3 : 4 2 0 0 0 / end = 1

 

✔️ 느낀 점

말 그대로 백트래킹은 쉬운데.. 중간의 저걸 구현하느라 시간을 너무 많이 소모해버렸다. 역시 골드 2..?

처음에 그냥 값을 복사할 때 계속 틀렸다고 나와서 찾아보니 깊은 복사를 하지 않아서 그렇다.

저번에 대충 훑어봐서 그냥 넘어가도 되겠다고 생각했는데 한번 정리하는 시간을 가져야 할 것 같다.

💻 코드

import sys, copy

n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
max_ = 0

def move(board, m):
    if m == 'U': # 위
        for y in range(n):
            end = 0
            for x in range(1, n):
                if board[x][y]:
                    tmp = board[x][y]
                    board[x][y] = 0
                    if board[end][y] == 0:
                        board[end][y] = tmp
                    elif board[end][y] == tmp:
                        board[end][y] *= 2
                        end += 1
                    else:
                        end += 1
                        board[end][y] = tmp
    if m == 'D': # 아래
        for y in range(n):
            end = n-1
            for x in range(n-2, -1, -1):
                if board[x][y]:
                    tmp = board[x][y]
                    board[x][y] = 0
                    if board[end][y] == 0:
                        board[end][y] = tmp
                    elif board[end][y] == tmp:
                        board[end][y] *= 2
                        end -= 1
                    else:
                        end -= 1
                        board[end][y] = tmp
    if m == 'L': # 왼쪽
        for x in range(n):
            end = 0
            for y in range(1, n):
                if board[x][y]:
                    tmp = board[x][y]
                    board[x][y] = 0
                    if board[x][end] == 0:
                        board[x][end] = tmp
                    elif board[x][end] == tmp:
                        board[x][end] *= 2
                        end += 1
                    else:
                        end += 1
                        board[x][end] = tmp
                        
    if m == 'R': # 오른쪽
        for x in range(n):
            end = n-1
            for y in range(n-2, -1, -1):
                if board[x][y]:
                    tmp = board[x][y]
                    board[x][y] = 0
                    if board[x][end] == 0:
                        board[x][end] = tmp
                    elif board[x][end] == tmp:
                        board[x][end] *= 2
                        end -= 1
                    else:
                        end -= 1
                        board[x][end] = tmp
        
    return board

def backtracking(board, cnt):
    global max_
    if cnt == 5:
        max_ = max(max_, max(map(max, board)))
        return
    
    for m in 'UDLR':
        tmp = move(copy.deepcopy(board), m)
        backtracking(tmp, cnt+1)
        
backtracking(board, 0)
print(max_)