[백준/파이썬] 12100번 2048 (Easy)

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

12100번: 2048 (Easy)

 

---

문제 해석

2048 게임 시스템을 구현해서 5번 이동할 때 최대가 되는 값을 구하는 문제

---

코드

1. 제출

n = int(input())

arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

def turn(current_arr):
    size = len(current_arr)
    temp_arr = [[0] * size for _ in range(size)]
    for r in range(size):
        for c in range(size):
            temp_arr[c][size - 1 - r] = current_arr[r][c]
    return temp_arr

def move(current_arr, direction):
    max_block = 0
    
    # print("current")
    # for k in current_arr:
    #     print(*k)
    # print()
    
    for _ in range(direction):
        current_arr = turn(current_arr)    
    
    next_arr = [[0] * n for _ in range(n)]
    
    for i in range(n):
        setting = 0
        new_step = []
        for j in range(n):
            if setting == 0:
                setting = current_arr[i][j]
            elif setting != 0 and current_arr[i][j] != 0:
                if setting == current_arr[i][j]:
                    # 합치기
                    new_step.append(setting * 2)
                    setting = 0
                else:
                    # 안합치기
                    new_step.append(setting)
                    setting = current_arr[i][j]
        # 마지막 한번 더
        new_step.append(setting)
        
        # 갱신
        for j in range(n):
            if j < len(new_step):
                next_arr[i][j] = new_step[j]
            else:
                next_arr[i][j] = 0
        max_block = max(max_block, max(next_arr[i]))

    # 원상 복구
    for i in range(4 - direction):
        next_arr = turn(next_arr)
    
    # print("next")
    # for k in next_arr:
    #     print(*k)
    # print()
    # print(max_block)
    
    return next_arr, max_block

answer = 0

def backtrack(arr, depth):    
    global answer
    if depth == 5:
        return

    for dir in range(4):
        new_arr, new_block = move(arr, dir)
        answer = max(answer, new_block)
        if new_arr == arr:
            continue
        backtrack(new_arr, depth + 1)
        

backtrack(arr, 0)
print(answer)

---

문제 풀이

게임의 시스템에서 이동할 수 있는 경우의 수는 상하좌우 4가지 경우이다.

 

가장 쉬운 방향인 좌측으로 이동하는 경우를 예를 들면

 

가장 좌측부터 하나씩 확인한다.

이때 현재값과 이전값을 세팅하며 탐색한다. 이때 이전값에는 0이 들어가지 않도록 한다.

a. 이전값과 현재값이 같다면 두 값을 더한 값을 임시 배열에 넣어준다. (이후 이전값은 0으로 갱신)

b. 이전값과 현재값이 다르다면 이전값을 임시 배열에 넣어준다. (이후 현재값을 이전값으로 갱신)

이때 한번 더 이전값을 확인해 배열에 넣어 마지막 값이 들어가지 않게 되는 예외 상황을 처리한다.

 

한 행의 갱신될 값을 임시 배열에 모두 저장했으므로 임시 배열을 차례로 넣어 새 배열을 갱신해준다.

이때 남은 공간은 0으로 갱신하는 과정을 꼭 해주어야 한다.

-> 모든 행에 대해 위 과정을 반복하면 좌측 방향으로 모든 값이 갱신됨을 확인 할 수 있다.

def move(current_arr, direction):
    max_block = 0
    
    for _ in range(direction):
        current_arr = turn(current_arr)    
    
    next_arr = [[0] * n for _ in range(n)]
    
    for i in range(n):
        setting = 0
        new_step = []
        for j in range(n):
            if setting == 0:
                setting = current_arr[i][j]
            elif setting != 0 and current_arr[i][j] != 0:
                if setting == current_arr[i][j]:
                    # 합치기
                    new_step.append(setting * 2)
                    setting = 0
                else:
                    # 안합치기
                    new_step.append(setting)
                    setting = current_arr[i][j]
        # 마지막 한번 더
        new_step.append(setting)
        
        # 갱신
        for j in range(n):
            if j < len(new_step):
                next_arr[i][j] = new_step[j]
            else:
                next_arr[i][j] = 0
        max_block = max(max_block, max(next_arr[i]))

    # 원상 복구
    for i in range(4 - direction):
        next_arr = turn(next_arr)
    
    return next_arr, max_block

위 과정을 구현한 코드이며, 갱신된 배열에서 최대값 또한 구해준다.

 

 

 

위  과정을 모든 방향으로 반복하는 코드를 짠다면 굉장히 복잡하다.

따라서 배열을 90도 회전하는 함수를 구현해 원하는 방향만큼 회전 후 갱신을 하고, 다시 원상복구 하는 방식으로 구현했다.

def turn(current_arr):
    size = len(current_arr)
    temp_arr = [[0] * size for _ in range(size)]
    for r in range(size):
        for c in range(size):
            temp_arr[c][size - 1 - r] = current_arr[r][c]
    return temp_arr

다음은 90 회전을 하는 코드이다.

 

이후 백트래킹으로 배열이 변하지 않는 경우를 가지치며 탐색하도록 구현해주었다.

-> 최적화

def backtrack(arr, depth):    
    global answer
    if depth == 5:
        return

    for dir in range(4):
        new_arr, new_block = move(arr, dir)
        answer = max(answer, new_block)
        if new_arr == arr:
            continue
        backtrack(new_arr, depth + 1)