[BOJ]12100. 2048(Easy)

문제:

2048 게임은 4x4 크기의 보드에서 혼자 즐기는 게임이다. 

 

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

 

이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 쵣 5번 이동해서 만들 수 있는 가장 큰 불록의 값을 구하는 프로그램을 작성하시오.

입력:

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

출력:

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

풀이방법:

최대 5번만 이동하면 되기 때문에 dfs를 사용해서 모든 경우를 탐색하고, 그 중 가장 최댓값을 찾아내도록 하면 된다.

반복문을 사용해서 상하좌우로 이동하게 만들었다.

import copy
 
def dfs(numbers,count):
    global answer
    if count==5:
        if max(max(numbers,key=lambda x : max(x))) > answer:
            answer = max(max(numbers,key=lambda x : max(x)))
        return
    count+=1
    for i in range(4):
        if i==0:
            numberT = copy.deepcopy(numbers)
            for j in range(N):
                tmp = -1
                temp = []
                for num in numberT[j]:
                    if num == 0:
                        continue
                    if len(temp)==0:
                        temp.append(num)
                        tmp = num
                    else:
                        if tmp==num and temp[-1]==num:
                            temp[-1]=num*2
                        else:
                            temp.append(num)
                        tmp = num
                if len(temp)!=N:
                    while len(temp)<N:
                        temp.append(0)
                numberT[j]=temp
            dfs(numberT,count)
        if i==1:
            numberT = copy.deepcopy(numbers)
            for j in range(N):
                tmp = -1
                temp = []
                for k in range(N-1,-1,-1):
                    if numberT[k][j]==0:
                        continue
                    if len(temp)==0:
                        temp.append(numberT[k][j])
                        tmp = numberT[k][j]
                    else:
                        if tmp == numberT[k][j] and temp[-1]==numberT[k][j]:
                            temp[-1]=numberT[k][j]*2
                        else:
                            temp.append(numberT[k][j])
                        tmp = numberT[k][j]
                temp.reverse()
                if len(temp)!=N:
                    while len(temp)<N:
                        temp.insert(0,0)
                for k in range(N):
                    numberT[k][j]=temp[k]
            dfs(numberT,count)
        elif i==2:
            numberT = copy.deepcopy(numbers)
            for j in range(N):
                tmp = -1
                temp = []
                for num in list(reversed(numberT[j])):
                    if num == 0:
                        continue
                    if len(temp)==0:
                        temp.append(num)
                        tmp = num
                    else:
                        if tmp == num and temp[-1]==num:
                            temp[-1]=num*2
                        else:
                            temp.append(num)
                        tmp = num
                if len(temp)!=N:
                    while len(temp)<N:
                        temp.append(0)
                numberT[j]=list(reversed(temp))
            dfs(numberT,count)
        elif i==3:
            numberT = copy.deepcopy(numbers)
            for j in range(N):
                tmp = -1
                temp = []
                for k in range(N):
                    if numberT[k][j] == 0:
                        continue
                    if len(temp)==0:
                        temp.append(numberT[k][j])
                        tmp = numberT[k][j]
                    else:
                        if tmp == numberT[k][j] and temp[-1]==numberT[k][j]:
                            temp[-1]=numberT[k][j]*2
                        else:
                            temp.append(numberT[k][j])
                        tmp = numberT[k][j]
                if len(temp)!=N:
                    while len(temp)<N:
                        temp.append(0)
                for k in range(N):
                    numberT[k][j]=temp[k]
            dfs(numberT,count)
 
N = int(input())
numbers = []
for _ in range(N):
    numbers.append(list(map(int,input().split())))
 
answer = -1
count = 0
dfs(numbers,count)
print(answer)

문제링크:

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)