Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 2048 (Easy)

[2048 (Easy)]

(240828 14:47 수정)

• 풀었다.

수정한 부분

1. 숫자가 있는 블럭에 대해 빈 칸으로 옮길 경우, 기존에 위치한 자리는 빈 공간이 된다는 점을 간과했다.
2. deepcopy 함수 cp를 만들어놓고 복사하지 않은 채 백트래킹을 했다.

개선된 부분

1. deque의 indexing은 $O(n/64)$이므로 미리 .popleft()하여 변수에 값을 할당한 뒤 사용했다.
2. 이전에 언급한 가지치기 포인트를 적용했다.
   1. 현재까지 계산된 최댓값을 $M$이라 할 때, 남은 이동횟수동안 어떤 경우에도 최댓값을 넘을 수 없는 경우
   2. 이동 후 보드의 모양이 그대로인 경우
      • 이동 후 보드의 모양이 그대로라는 것은, 이동 횟수만 1 깎이고 아무런 이득을 보지 못하는 것을 의미한다. 다른 방향으로 이동해서 최댓값을 갱신해 줄 수도 있지 않을까 하고 생각할 수 있는데, 그럴 땐 처음부터 그 방향으로 이동하면 이동 횟수가 하나 더 있는 셈이다. 오히려 최댓값 갱신의 여지가 많아진다.
   • 이러한 경우에 대해 조기종료하도록 백트래킹 코드를 짰는데, a. 의 경우 매번 $O(n^2)$의 시간이 걸려서인지 오히려 실행시간에서는 느렸다.

Solution. $O(n^2 \cdot {_4H_5})$

from collections import deque
import sys
input = sys.stdin.readline

def cp(board):
    return [r[:] for r in board]

def up(board):
    for j in range(n):
        blank = deque()
        exist = []
        for i in range(n):
            if not board[i][j]: blank.append(i)
            else:
                if exist and exist[1] == board[i][j]:
                    board[exist[0]][j] <<= 1; board[i][j] = 0
                    blank.append(i)
                    exist = []
                else: exist = [i, board[i][j]]

                if blank and exist:
                    b = blank.popleft() # O(1)
                    exist[0] = b # exist[0] = blank[0] # deque indexing : O(n/64)
                    board[b][j], board[i][j] = board[i][j], 0
                    blank.append(i)
    
    return board

def down(board):
    for j in range(n):
        blank = deque()
        exist = []
        for i in range(n-1, -1, -1):
            if not board[i][j]: blank.append(i)
            else:
                if exist and exist[1] == board[i][j]:
                    board[exist[0]][j] <<= 1; board[i][j] = 0
                    blank.append(i)
                    exist = []
                else: exist = [i, board[i][j]]

                if blank and exist:
                    b = blank.popleft()
                    exist[0] = b
                    board[b][j], board[i][j] = board[i][j], 0
                    blank.append(i)
    
    return board

def left(board):
    for i in range(n):
        blank = deque()
        exist = []
        for j in range(n):
            if not board[i][j]: blank.append(j)
            else:
                if exist and exist[1] == board[i][j]:
                    board[i][exist[0]] <<= 1; board[i][j] = 0
                    blank.append(j)
                    exist = []
                else: exist = [j, board[i][j]]

                if blank and exist:
                    b = blank.popleft()
                    exist[0] = b
                    board[i][b], board[i][j] = board[i][j], 0
                    blank.append(j)      

    return board

def right(board):
    for i in range(n):
        blank = deque()
        exist = []
        for j in range(n-1, -1, -1):
            if not board[i][j]: blank.append(j)
            else:
                if exist and exist[1] == board[i][j]:
                    board[i][exist[0]] <<= 1; board[i][j] = 0
                    blank.append(j)
                    exist = []
                else: exist = [j, board[i][j]]

                if blank and exist:
                    b = blank.popleft()
                    exist[0] = b
                    board[i][b], board[i][j] = board[i][j], 0
                    blank.append(j)

    return board

def backtracking(board, d, mx):
    if d == 5: return max(map(max, board))

    for move in [up, down, left, right]:
        nxt = move(cp(board))
        if nxt == board or max(map(max, nxt))*1<<5-d <= mx: continue
        mx = max(mx, backtracking(nxt, d+1, mx))

    return mx
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

print(backtracking(board, 0, max(map(max, board))))

• up(), down(), left(), right()
  • up()을 기준으로 설명하면,
  • 위로 이동하는 경우는 각 열의 상태는 독립적이다. 즉, 위/아래로만 어떤 변화가 발생했으면 발생했지, 왼쪽/오른쪽으로는 어떠한 변화도 발생하지 않는다. 이를 생각하여 각 열에 대해 반복하기 위해 for j in range(n)을 이용했다.
  • 빈 칸을 queue로 관리한다. 빈 칸이 아닌 칸을 발견하면 가장 먼저 발견한 빈 칸으로 당겨주기 위함이다.
  • merge를 구현하기 위해 exist를 이용했다. 숫자인 칸을 발견하면 exist 에 [index, value] 형태로 저장해 놓고, 그 다음 순회에서 숫자인 칸을 다시 발견한다면, 이미 발견한 숫자인 칸이 존재하며 그 값이 현재의 값과 같을 땐 merge를 수행한다. 이 때, merge를 수행한 현재의 칸은 빈 칸이 되어 blank queue에 인덱스를 push해주고, exist를 비워줘야 한다.
  • 이후 빈 칸이 존재하고, 위에 exist 값이 존재할 때 (존재하지 않을 땐 이미 merge되었고 그 위치에 대한 처리가 merge 단계에서 이미 끝났다는 것을 의미하므로) 순회 중 가장 먼저 발견한 빈 칸과 그 칸을 swap해줌으로써 위로 이동한 것처럼 만들어 준다. 이 때, 기존 칸은 이동 후 빈 칸이 되기 때문에 blank queue에 인덱스를 push해줘야 한다.
• backtracking()
  • Base condition : d == 5
  • 각 방향으로 이동하되, deepcopy해가면서 이동해야 서로 다른 이동에 독립적으로 작동한다.
  • 위에서 언급했던 가지치기 포인트들이 있다.
    1. 이동 후 보드의 모양이 그대로인 경우는 이동 횟수만 1 깎이고 아무런 이득을 보지 못하는 것을 의미한다. 다른 방향으로 이동해서 최댓값을 갱신해 줄 수도 있지 않을까 하고 생각할 수 있는데, 그럴 땐 처음부터 그 방향으로 이동하면 이동 횟수가 하나 더 있는 셈이다. 오히려 최댓값 갱신의 여지가 많아진다.
    2. 현재까지 계산된 최댓값을 $M$이라 할 때, 남은 이동 횟수의 $2^{5-d}$ 배 이하라는 것은 최댓값 갱신의 여지가 없다는 의미이므로 조기종료한다.
       • 하지만 이는 매번 $O(n^2)$의 시간이 추가로 소요되기 때문에 오히려 실제 실행 시간은 더 느렸다.

---

(풀기 전 내용, 240828 02:30)

• 거의 풀어가는 것 같은데, left, right 구현에서 틀린 부분이 있는 것 같다.
• 구현, 시뮬레이션 문제에서 내가 많이 약한 것 같다. 꼭 보완해서 무기로 만들자!
• 추가로 아직 구현하지 못한 가지치기 포인트들이 있다.

  1. 현재까지 계산된 최댓값을 $M$에서, 남은 이동횟수동안 어떻게 합쳐도 최댓값을 넘을 수 없는 상황 → return

  2. 이동 후 보드의 모양이 그대로일 때 → return

     (아무런 변화 없이 이동 횟수만 1만 소모하는 것이므로)

• 내일 다시 풀어보겠,,,습니다!!

---