백준 온라인 저지, 구현/12100번: 2048(easy)(파이썬 / 백준 골드문제)

문제

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

 

문제 정의

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

 

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

 

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

 

입력

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

 

 

 

출력

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

 

 

예제 입력 1

3
2 2 2
4 4 4
8 8 8

 

예제 출력 1

16

 

접근 방법

- 주어진 보드에서 상하좌우로 총 5번씩 움직인 뒤, 나타난 결과 중 가장 큰 블록을 출력한다.

 

시간복잡도

- 연산횟수: 400(보드의 크기) x 4 ^ 5 (상하좌우를 총 5번 움직였을 때의 경우의 수) = 최대 약 410만번의 연산

 

코드

# https://www.acmicpc.net/problem/12100
# 접근방법
# 주어진 보드에서 상하좌우로 총 5번씩 움직인 뒤, 나타난 결과 중 가장 큰 블록을 출력한다.
# 시간복잡도: 400(보드의 크기) x 4 ^ 5 (상하좌우를 총 5번 움직였을 때의 경우의 수) = 최대 약 410만번의 연산
import sys
from itertools import product

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

def move(board):
    # board_ = [l[:] for l in board]
    for x in list(product([1, 2, 3, 4], repeat=5)):
        board_ = [l[:] for l in board]
        for i in x:
            if i == 1:
                move_right(board_)
            elif i == 2:
                move_left(board_)
            elif i == 3:
                move_up(board_)
            else:
                move_down(board_)
    # move_right(board_)
    # move_right(board_)
    # move_right(board_)
    # move_right(board_)
    # move_down(board_)


def move_right(board):
    global result

    for i in range(n):
        array = []
        for x in [x for x in board[i] if x > 0]: # 가로로 움직이는 경우
            array.append(x)
        j = 0
        while len(array) - 1 > j:
            if array[len(array) - 1 - j] == array[len(array) - 2 - j]: # 오른쪽으로 움직이는 경우 오른쪽을 기준으로 합친다.
                array[len(array) - 1 - j] *= 2
                array[len(array) - 2 - j] = 0
                j += 1
            j += 1
        
        array = [x for x in array if x > 0]
        board[i] = [0 for _ in range(n)]
        for j in range(len(array)):
            board[i][n - 1 - j] = array[len(array) - 1 - j]
            result = max(result, array[len(array) - 1 - j])
    


def move_left(board):
    global result

    for i in range(n):
        array = []
        for x in [x for x in board[i] if x > 0]: # 가로로 움직이는 경우
            array.append(x)
        j = 0
        while len(array) - 1 > j:
            if array[j] == array[j + 1]: # 왼쪽으로 움직이는 경우
                array[j] *= 2
                array[j + 1] = 0
                j += 1
            j += 1

        array = [x for x in array if x > 0]
        board[i] = [0 for _ in range(n)]
        for j in range(len(array)):
            board[i][j] = array[j]
            result = max(result, array[j])
    

def move_up(board):
    global result

    for i in range(n):
        array = []
        for j in range(n): # 세로로 움직이는 경우
            array.append(board[j][i])
        array = [x for x in array if x > 0]

        j = 0
        while len(array) - 1 > j:
            if array[j] == array[j + 1]: # 위쪽으로 움직이는 경우
                array[j] *= 2
                array[j + 1] = 0
                j += 1
            j += 1

        array = [x for x in array if x > 0]
        for j in range(n):
            board[j][i] = 0
        for j in range(len(array)):
            board[j][i] = array[j]
            result = max(result, array[j])



def move_down(board):
    global result
    
    for i in range(n):
        array = []
        for j in range(n): # 세로로 움직이는 경우
            array.append(board[j][i])
        array = [x for x in array if x > 0]
        j = 0
        while len(array) - 1 > j:
            if array[len(array) - 1 - j] == array[len(array) - 2 - j]: # 아래쪽으로 움직이는 경우 오른쪽을 기준으로 합친다.
                array[len(array) - 1 - j] *= 2
                array[len(array) - 2 - j] = 0
                j += 1
            j += 1
        array = [x for x in array if x > 0]
        for j in range(n):
            board[j][i] = 0
        for j in range(len(array)):
            board[n - 1 - j][i] = array[len(array) - 1 - j]
            result = max(result, array[len(array) - 1 - j])

result = 0
move(board)
print(result)