[BOJ] 12100 2048 (Eazy)

date

Jul 7, 2023

slug

boj-12100

author

status

Public

문제 링크

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

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

문제풀이

상하좌우에 따른 이동코드를 만든 후에

동남 방향 같은 경우 순방향 탐색

탐색에서 0이 있는 경우 temp_list에 appendleft(0) 아닌경우 append(v)

서북 방향 같은 경우 역방향 탐색

탐색에서 0이 있는 경우 temp_list에 append(0) 아닌경우 appendleft(v)

모든 탐색 경우에 대하여 다음 방향의 값이 0인경우 continue 다음 방향의 값이 0이 아닌 경우에 다음 방향의 값이 현재 값과 같은경우 2를 곱해서 pending_list에 넣음 다른경우 그냥 넣음
pending_list에 대하여

배열의 길이가 N보다 작은경우 N과 같을때까지 0을 뒤에 채워넣는다 ”동남의경우 역방향 순회처리”, 남,북 같은 경우 모든 배열 순회하면서 copy 동,서의 경우 copy.deepcopy로 copy

pending_list 초기화

백트래킹을 통해 모든 경우를 탐색하면서 process() 코드 같은경우에는 (상하좌우 이동) arr 자체를 바꾸기 때문에 반환값이 없더라도 전후의 배열 값이 바뀌게 된다. 그러므로 process전후로 값이 바뀌지 않게 하기위해 배열 복사를 통해서 값이 바뀌지 않게 함 가장 큰 원소를 리턴

상화좌우에 따른 이동 결과를 만들 때는 0을 먼저 처리해줘야 하기 때문에 deque() 구조 사용

백트래킹을 통해 모든 경우를 탐색하면서 가장 큰 원소를 리턴하기 위해서는

이전의 상태를 저장할 필요가 있다. 즉

의 공간복잡도가 필요하다

또한 배열복사를 할때는 copy.deepcopy()를 통해 복사하여야 한다 (깊은 복사)

값 자체를 복사해서 새로운 메모리를 차지

그냥 =를 통해 복사하게 되면 얕은복사( 주소값 자체가 복사가 됨 ) 백트래킹 불가

파이썬 문제풀이 코드


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

N = int(input())

def process(arr, direction): # 0123 동남서북
    
    pending_list = []
    if direction <= 0:
        
        for i in range(N):
            temp_list = deque()
            for j in range(N):
                if arr[i][j] == 0:
                    temp_list.appendleft(0)
                else:
                    temp_list.append(arr[i][j])
            arr[i] = copy.deepcopy(list(temp_list))
                    
        for i in range(N):
            j = N-1
            while j >= 0:
                if arr[i][j] == 0:
                    j = j-1
                    continue
                if j-1 < 0:
                    pending_list.append(arr[i][j])
                else:
                    if arr[i][j] == arr[i][j-1]:
                        pending_list.append(2*arr[i][j])
                        j = j-1 # 계산됬기 때문에 건너뜀
                    else:
                        pending_list.append(arr[i][j])
                j = j-1
            while len(pending_list) != N:
                pending_list.append(0)
            pending_list = pending_list[::-1]
            arr[i] = pending_list
            pending_list = []
        return arr
    elif direction == 1:
        for j in range(N): # 0 처리
            temp_list = deque()
            for i in range(N):
                if arr[i][j] == 0:
                    temp_list.appendleft(0)
                else:
                    temp_list.append(arr[i][j])
            temp_list = list(temp_list)
            for temp in range(len(temp_list)): # 남쪽이라 순방향 0
                arr[temp][j] = temp_list[temp]
        for j in range(N):
            i = N-1
            while i >= 0:
            
                if arr[i][j] == 0:
                    
                    i = i-1
                    continue
                
                if i-1 < 0:
                    pending_list.append(arr[i][j])
                else:
                    if arr[i][j] == arr[i-1][j]:
                        pending_list.append(2*arr[i][j])
                        i = i-1 # 계산됬기 때문에 건너뜀
                    else:
                        pending_list.append(arr[i][j])
                i = i-1
            while len(pending_list) != N:
                pending_list.append(0)
            
            pending_list = pending_list[::-1]            
            for pend in range(len(pending_list)):
                arr[pend][j] = pending_list[pend]
                    
            
            pending_list = []
            
        return arr

    if direction == 2:
        for i in range(N):
            temp_list = deque()
            for j in range(N-1, -1, -1):
                if arr[i][j] == 0:
                    temp_list.append(0)
                else:
                    temp_list.appendleft(arr[i][j])
            arr[i] = copy.deepcopy(list(temp_list))
        # print(arr)
        for i in range(N):
            j = 0
            while j <= N-1:
                if arr[i][j] == 0:
                    j = j + 1
                    continue 
                if j+1 > N-1:
                    pending_list.append(arr[i][j])
                else:
                    if arr[i][j] == arr[i][j+1]:
                        pending_list.append(2*arr[i][j])
                        j = j+1 # 계산됬기 때문에 건너뜀
                    else:
                        pending_list.append(arr[i][j])
                j = j+1
            while len(pending_list) != N:
                pending_list.append(0)
            # pending_list = pending_list[::-1]
            arr[i] = pending_list
            pending_list = []
        return arr

    elif direction == 3:
        for j in range(N): # 0 처리
            temp_list = deque()
            for i in range(N-1, -1, -1):
                if arr[i][j] == 0:
                    temp_list.append(0)
                else:
                    temp_list.appendleft(arr[i][j])
                
            temp_list = list(temp_list)
            for temp in range(len(temp_list)): # 북쪽이라 역방향 0
                arr[temp][j] = temp_list[temp]
                
        for j in range(N):
            i = 0
            while i <= N-1: 
                if arr[i][j] == 0:
                    i = i + 1
                    continue     
                if i+1 > N-1:
                    pending_list.append(arr[i][j])
                else:
                    if arr[i][j] == arr[i+1][j]:
                        pending_list.append(2*arr[i][j])
                        i = i+1 # 계산됬기 때문에 건너뜀
                    else:
                        pending_list.append(arr[i][j])
                i = i+1
            while len(pending_list) != N:
                pending_list.append(0)
            pending_list = pending_list            
            for pend in range(len(pending_list)):
                arr[pend][j] = pending_list[pend]
            
            pending_list = []
        return arr
                
        
max_value = 0
# arr_copy = []

max_list = []
def backtracking(p, K):
    t = copy.deepcopy(p)
    global max_value
    # arr_copy = copy.deepcopy(arr)
    if K == 0:
        max_list.append(max(list(map(max, t))))
        return 
    
    for i in range(4): # 상하좌우
        l = copy.deepcopy(t)
        arr_copy = copy.deepcopy(process(t, i))
        t = copy.deepcopy(l)
        max_list.append(max(list(map(max, arr_copy))))
        backtracking(arr_copy, K-1)
    
    # print(K)
    
    # print(max_value)
    max_list.append(max(list(map(max, t))))
    # print(t, K)
    return
            
def main():    
    
    arr = []
    for _ in range(N):
        li = list(map(int, input().split()))
        arr.append(li)
        
    
    # print(arr)
    p = copy.deepcopy(arr)
    backtracking(p, 5)
    print(max(max_list))
    # print(arr)
        
    # print(max_value)
    
    # arr = process(arr, 2)
    # arr = process(arr, 3)
    # arr = process(arr, 2)
    # arr = process(arr, 1)
    # arr = process(arr, 0)    
      
    # print(arr)
    # arr = process(arr, 3)
    # print(arr)
    
main()

시간복잡도

O(N^2)

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

예제 입력

예제 출력


4
0 64 2 1024
2 512 8 0
0 32 512 256
64 64 8 2

23210, 서북서남동

알고리즘 분류

구현

브루트포스 알고리즘

시뮬레이션

백트래킹