백준 12100 2048(easy) 파이썬

아이디어: dfs를 통해 5번 움직이는 모든 경우의수를 탐색.  상, 하, 좌, 우로 움직이는 경우를 5번 깊이 까지 DFS로 탐색하는 것.

 

import sys

from copy import deepcopy

input = sys.stdin.readline

# 입력

n = int(input())

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

answer = 0

# 위로

def up(board):

    for j in range(n):

        pointer = 0

        for i in range(1, n):

            if board[i][j]:

                tmp = board[i][j]

                board[i][j] = 0

                # 3가지 경우로 나눠서 처리

                # 포인터가 가리키는 수가 0일 때

                if board[pointer][j] == 0:

                    board[pointer][j] = tmp

                # 포인터가 가리키는 수와 현재 위치의 수가 같을 때

                elif board[pointer][j]  == tmp:

                    board[pointer][j] *= 2

                    pointer += 1

                # 포인터가 가리키는 수와 현재 위치의 수가 다를 때

                else:

                    pointer += 1

                    board[pointer][j] = tmp

    return board

# DOWN

def down(board):

    for j in range(n):

        pointer = n - 1

        for i in range(n - 2, -1, -1):

            if board[i][j]:

                tmp = board[i][j]

                board[i][j] = 0

                # 포인터가 가리키는 수가 0일 때

                if board[pointer][j] == 0:

                    board[pointer][j] = tmp

                # 포인터가 가리키는 수와 현재 위치의 수가 같을 때

                elif board[pointer][j]  == tmp:

                    board[pointer][j] *= 2

                    pointer -= 1

                # 포인터가 가리키는 수와 현재 위치의 수가 다를 때

                else:

                    pointer -= 1

                    board[pointer][j] = tmp

    return board

# LEFT

def left(board):

    for i in range(n):

        pointer = 0

        for j in range(1, n):

            if board[i][j]:

                tmp = board[i][j]

                board[i][j] = 0

                # 포인터가 가리키는 수가 0일 때

                if board[i][pointer] == 0:

                    board[i][pointer] = tmp

                # 포인터가 가리키는 수와 현재 위치의 수가 같을 때

                elif board[i][pointer]  == tmp:

                    board[i][pointer] *= 2

                    pointer += 1

                # 포인터가 가리키는 수와 현재 위치의 수가 다를 때

                else:

                    pointer += 1

                    board[i][pointer]= tmp

    return board

# RIGHT

def right(board):

    for i in range(n):

        pointer = n - 1

        for j in range(n - 2, -1, -1):

            if board[i][j]:

                tmp = board[i][j]

                board[i][j] = 0

                # 포인터가 가리키는 수가 0일 때

                if board[i][pointer] == 0:

                    board[i][pointer] = tmp

                # 포인터가 가리키는 수와 현재 위치의 수가 같을 때

                elif board[i][pointer]  == tmp:

                    board[i][pointer] *= 2

                    pointer -= 1

                # 포인터가 가리키는 수와 현재 위치의 수가 다를 때

                else:

                    pointer -= 1

                    board[i][pointer] = tmp

    return board

# DFS

def dfs(board, cnt):

    if cnt == 5:

        # 2차원 배열 요소 중 가장 큰 값 반환

        return max(map(max, board))

    # 상, 하, 좌, 우로 움직여 리턴한 값들 중 가장 큰 값 반환

    # board를 꼭 deepcopy하여 함수를 거친 board값이 다음 함수에 들어가지 못하도록 해주어야 한다.

    return max(dfs(up(deepcopy(board)), cnt + 1), dfs(down(deepcopy(board)), cnt + 1), dfs(left(deepcopy(board)), cnt + 1), dfs(right(deepcopy(board)), cnt + 1))

print(dfs(board, 0))

#deepcopy를 하는 이유는 보드가 Call By Reference로 호출되기 때문에 board의 원본은 그대로 유지하기 위해서이다.