[BOJ] 12100. 2048 (Easy) (🥇, 백트래킹, 시뮬레이션)

🔗

풀이

문제에서 알려준 2048 게임 룰은 아래와 같다.

이동하는 방향으로 같은 숫자가 연속으로 2개 있다면 합쳐진다.
(단, 빈칸은 고려햐지 않는다.)

• 그림에선 왼쪽으로 이동
  

한 방향으로 여러개가 있다면 이동하는 방향 쪽에 위치한 2개를 먼저 합친다.

• 그림에선 위쪽으로 이동
  

이미 한 번의 이동으로 다른 숫자와 합쳐진 숫자는 또 다른 숫자와는 합쳐질 수 없다.

• 2+2는 4가 되지만 4+4가 8이될 수는 없다. 이미 위로 이동하면서 2,2가 각각 합쳐져서 4가 되었기 때문.
  

보드판의 최대 크기는 20x20이며 총 5번 진행가능하다. 각각의 경우에 상하좌우 모두 고려해야 하므로 4^5 = 대략 4천번 이하로 완전탐색으로 진행 가능하다. 모든 경우의 수를 구하고 최대값을 구하면 된다.

오른쪽으로 탐색하면서 찾기(왼쪽으로 이동하는 경우)

왼쪽으로 이동하는 경우가 각 값을 탐색하기 가장 편하기 때문에 기준으로 정했다. 가장 왼쪽에 위치한 숫자를 i로 설정하고 그 다음 값을 j로 설정하여 j를 1씩 증가시키며 1) 같은 값이 있는지 2) 다른 값이 있는지를 탐색했다. 만약 같거나 다른 값이 없고 전부다 빈칸이라면 탐색을 종료했다.

탐색의 기준이 되는 값 i가 빈 칸이라면 그대로 넘어간다.

빈 칸이 아니라면 다음 값부터 시작해서 값을 탐색한다. 만약 j에 위치한 값이 빈 칸이면 마찬가지로 넘어간다. 빈 칸이 아니라면 두 개의 경우로 나뉘게 된다. 같은 숫자인 경우는 더하고, 다른 숫자인 경우는 그 숫자를 기준으로 변경해야 한다.

블록 이동

기본적으로 한쪽 방향으로 모든 블록을 이동시키게 되면 빈 칸이 아닌 값들만 한쪽으로 쌓이게 된다. 빈 칸을 제외한 값들만 하나씩 차례대로 구해서 임시배열에 추가하고, 모두 구했다면 전체 열의 길이만큼 빈칸을 추가하는 방식으로 구현했다.

배열 돌리기

왼쪽 -> 오른쪽으로 탐색해나가는 코드가 기준이다. 즉 모든 블록이 왼쪽 방향으로 이동하는 경우가 기준이 된다. 위, 아래, 오른쪽으로 이동하는 경우들은 2차원 배열을 회전시켜서 계산한 후 다시 회전시킨 값을 반환했다.

최종 코드

# 2048 (Easy)

def rotate(dir, board):
    if dir == 1: # UP
        arr = move(list(map(list, zip(*board))))
        return list(map(list, zip(*arr)))
    elif dir == 2: # DOWN
        arr = move(list(map(list, zip(*board[::-1]))))
        return list(map(list, zip(*arr)))[::-1]
    elif dir == 3: # RIGHT
        arr = move(row[::-1] for row in board)
        return [row[::-1] for row in arr]
    else: # LEFT
        return move(board)
    
def move(board):
    arr = []
    for row in board:
        i = -1
        tmp = []
        while i<N-1:
            i += 1
            if not row[i]:
                continue
            j = i
            while j<N-1:
                j += 1
                # 빈 칸인 경우
                if not row[j]:
                    continue
                # 같은 값인 경우
                if row[j] == row[i]:
                    tmp.append(2*row[i])
                    i = j
                    break
                # 다른 값인 경우
                if row[j] != row[i]:
                    tmp.append(row[i])
                    i = j-1
                    break
            # 아무런 값도 찾지 못한 경우 그냥 그 값을 추가
            else:
                tmp.append(row[i])
                break
        arr.append(tmp+[0]*(N-len(tmp)))
    return arr

def game(round, board):
    global answer
    if round == 5:
        for row in board:
            answer = max(answer, max(row))
        return 

    for d in range(4):
        tmp = rotate(d, [row[:] for row in board])
        game(round+1, tmp)

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

answer = 0
game(0, board)
print(answer)