[백준] 2048

그리디 문제로 소개되어 있지만 해시 함수를 이용한 DP 풀이법으로 풀어보았다.

from collections import defaultdict
class Board:
    board = []
    n = 0
    case = defaultdict(list)

    def __init__(self, n):
        self.n = n

    def make_set_by_line(self,line):
        self.board.append(line)

    def make_board(self,cur_board,dir):
        new_board = []
        if dir == 0:#북
            cur_board = list(map(list,zip(*cur_board)))
            #print('0',cur_board)
            for line in cur_board:
                line = line[::-1]
                new_line = self.get_new_line(line)
                new_board.append(new_line)
            #print('0',new_board)
            new_board = list(map(list,zip(*new_board)))

        elif dir == 1:#동 2 2 2 -> 0 2 4 / 2 4 8 -> 2 4 8
            for line in cur_board:
                new_line = self.get_new_line(line)
                new_line = new_line[::-1]
                new_board.append(new_line)

        elif dir == 2:#남
            cur_board = list(map(list, zip(*cur_board)))
            #print('2',cur_board)
            for line in cur_board:
                new_line = self.get_new_line(line)
                new_line = new_line[::-1]
                new_board.append(new_line)
            new_board = list(map(list, zip(*new_board)))

        elif dir == 3:#서 02240 -> 44000
            for line in cur_board:
                line = line[::-1]
                new_line = self.get_new_line(line)
                new_board.append(new_line)
        return new_board

    def get_new_line(self, line):
        new_line = []
        line = [i for i in line if i != 0]
        #print(line)
        if line:
            cur_num = line.pop()
        else:
            return [0]*n
        while 1:
            if line:
                next_num = line.pop()
            else:
                next_num = -1
            if cur_num == next_num:
                new_line.append(cur_num + next_num)
            else:
                new_line.append(cur_num)
                if next_num != -1:
                    line.append(next_num)
                else:
                    break
            if line:
                cur_num = line.pop()
            else:
                break
        new_line += [0] * (n - len(new_line))
        return new_line
        
    def play(self, dirs):
        if len(dirs) > 4:
            return
        else:
            for i in range(4):
                self.case[dirs+str(i)] = self.make_board(self.case[dirs],i)
                self.play(dirs+str(i))

n = int(input())
board = Board(n)

tmp_board = []
for _ in range(n):
    board.make_set_by_line(list(map(int,input().split())))

board.case[""] = board.board

board.play("")

print(max([max(sum(brd,[])) for brd in board.case.values()]))

ㅋㅋㅋ... 한 3시간은 넘게 걸린듯 하다.

 

여기서 몇가지 새롭게 알아간 기법들...

new_board = list(map(list, zip(*new_board)))
# 2차원 list의 세로와 가로를 바꿔주는 방법

sum(brd,[])
# 2차웜 list를 평탄화해주는 방법

2차원 리스트를 활용해야 하는 문제들은 항상 어렵다...