[백준] 2048 (Easy)

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

12100번: 2048 (Easy)

구현 문제입니다.

 

문제부터 아주 간단하게 요약하면, 흔히 우리가 플레이 하는 2048을 문제에서 주어진 조건에 맞게 implement 하는 문제입니다. 이 때, 총 5번의 이동을 거친후 남게 될 수 있는 가장 큰 숫자가 무엇인지를 return 해야 합니다. 

 

<Solution>

move 함수는 현재 보드의 상태와, 이동방향을 받아서 새로운 보드를 만들어주는 함수입니다. 이 move 함수만 올바르게 implement 하면, dfs등의 완전 탐색을 통해 문제를 해결할 수 있습니다. 

 

list를 순회하면서 합칠수 있는 것들을 합치도록 구현하였습니다. 상하좌우로 움직이는 경우에 중복되는 코드가 많이 있는데 이러한 코드들은 압축시키면 좀 더 깔끔해 질 것 같습니다. 

 

실제 구현은 아래와 같습니다.

import sys

N = int(sys.stdin.readline().rstrip())

# build array
array = []
for _ in range(N):
    array.append(list(map(int,sys.stdin.readline().rstrip().split())))

def move(array, direction): 
    new_array = []
    if direction == 0: # left
        for line in array:
            tmp = []
            e1 = 0
            e2 = 0
            for i in range(N):
                if line[i] != 0 and e1 == 0:
                    e1 = line[i]
                elif line[i] != 0 and e1 != 0:
                    e2 = line[i]
                    if e1 == e2:
                        tmp.append(e1+e2)
                        e1 = 0
                        e2 = 0
                    else:
                        tmp.append(e1)
                        e1 = e2
                        e2 = 0
                else:
                    continue
            if e1 != 0:
                tmp.append(e1)
            for _ in range(N-len(tmp)):
                tmp.append(0)
            new_array.append(tmp)
    elif direction == 1: # right
        for line in array:
            line.reverse()
            tmp = []
            e1 = 0
            e2 = 0
            for i in range(N):
                if line[i] != 0 and e1 == 0:
                    e1 = line[i]
                elif line[i] != 0 and e1 != 0:
                    e2 = line[i]
                    if e1 == e2:
                        tmp.append(e1+e2)
                        e1 = 0
                        e2 = 0
                    else:
                        tmp.append(e1)
                        e1 = e2
                        e2 = 0
                else:
                    continue
            if e1 != 0:
                tmp.append(e1)
            for _ in range(N-len(tmp)):
                tmp.append(0)
            tmp.reverse()
            new_array.append(tmp)
    elif direction == 2: # up
        for line in list(map(list, zip(*array))):
            tmp = []
            e1 = 0
            e2 = 0
            for i in range(N):
                if line[i] != 0 and e1 == 0:
                    e1 = line[i]
                elif line[i] != 0 and e1 != 0:
                    e2 = line[i]
                    if e1 == e2:
                        tmp.append(e1+e2)
                        e1 = 0
                        e2 = 0
                    else:
                        tmp.append(e1)
                        e1 = e2
                        e2 = 0
                else:
                    continue
            if e1 != 0:
                tmp.append(e1)
            for _ in range(N-len(tmp)):
                tmp.append(0)
            new_array.append(tmp)
        new_array = list(map(list, zip(*new_array)))
    else: # down (3)
        for line in list(map(list, zip(*array))):
            line.reverse()
            tmp = []
            e1 = 0
            e2 = 0
            for i in range(N):
                if line[i] != 0 and e1 == 0:
                    e1 = line[i]
                elif line[i] != 0 and e1 != 0:
                    e2 = line[i]
                    if e1 == e2:
                        tmp.append(e1+e2)
                        e1 = 0
                        e2 = 0
                    else:
                        tmp.append(e1)
                        e1 = e2
                        e2 = 0
                else:
                    continue
            if e1 != 0:
                tmp.append(e1)
            for _ in range(N-len(tmp)):
                tmp.append(0)
            tmp.reverse()
            new_array.append(tmp)
        new_array = list(map(list, zip(*new_array)))

    return new_array

answer = 0

def dfs_search(times, array):
    global answer
    if times >= 5:
        if max(map(max, array)) > answer:
            answer = max(list(map(max, array)))
            return
        else:
            return
    for i in range(4):
        dfs_search(times+1, move(array, i))

dfs_search(0, array)
print(answer)