[ 12100 ] [ stack, product ] 2048 (Easy)

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

12100번: 2048 (Easy)

 

이게 이지야? 이지 같은 소리 하네 증말

---

문제 설명

---

1. 전체 이동 횟수가 최대 5번이므로 전체 대략 4^5제곱 정도의 케이스가 나온다.
   1. 1번, 2번, 3번, 4번 이동하는 케이스의 경우 결국 5번 이동할동안 거쳐가는 부분이므로 패스
2. 위, 아래, 좌, 우 이동 파트를 구현한다.
   1. 구현하는 방식은, 이동시킨 결과물을 저장할 새로운 배열을 만들어준 다음, 예시로 위쪽 이동의 경우 각 열마다 위에서 아래로 반복문을 돌면서 스택에 넣어준다.
   2. 스택의 맨 위 요소와 현재 넣는 요소의 값이 같으면 합쳐주고, 추후에 합쳐주지 않기 위해 플래그를 따로 걸어둔다.
   3. 스택의 맨 위 요소와 현재 넣는 요소의 값이 다르면 그냥 스택에 넣어주면 된다.
   4. 하나의 열에 대한 반복문이 종료되었으면 스택의 요소들을 첫번째 요소부터 새로운 배열의 맨 위에서부터 넣어주면 된다.
   5. 이 과정을 전체 열에 대해서 적용하면 위쪽 방향 이동이 종료된다.
   6. 위와 같은 방식으로 위, 아래, 좌, 우 이동 파트를 구현한다.
3. 전체 케이스에 대해서 실제로 이동시켜 보면서 이동시킬 때마다 배열의 최댓값을 갱신시켜주면 된다.
   • 대략 4^5제곱 정도 케이스가 나온다고 보면 된다.

---

소스 코드

---

import sys
import copy

from itertools import product

input = lambda : sys.stdin.readline().rstrip()
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]

def up_down_movement(way, matrix):
    # way : 1, 2, 각각 위, 아래
    N = len(matrix)
    if way == 1:
        start, end, add = 0, N, 1
    elif way == 2:
        start, end, add = N-1, -1, -1

    new_matrix = [[0] * len(matrix) for _ in range(len(matrix))]
    for j in range(N):
        stack = []
        for i in range(start, end, add):
            if not stack and matrix[i][j] != 0:
                stack.append([matrix[i][j], False])
            elif stack and stack[-1][1] == False and stack[-1][0] == matrix[i][j]:
                latest, _ = stack.pop()
                stack.append([matrix[i][j] + latest, True])
            elif stack and matrix[i][j] != 0:
                stack.append([matrix[i][j], False])

        for i in range(len(stack)):
            if way == 1:
                new_matrix[i][j] = stack[i][0]
            elif way == 2:
                new_matrix[N-1-i][j] = stack[i][0]
                
    return new_matrix

def left_right_movement(way, matrix):
    # way가 각각 1,2일때 왼쪽, 오른쪽
    N = len(matrix)

    if way == 1:
        start, end, add = 0, N, 1
    elif way == 2:
        start, end, add = N-1, -1, -1

    new_matrix = [[0] * len(matrix) for _ in range(len(matrix))]
    for i in range(N):
        stack = []
        for j in range(start, end, add):
            if not stack and matrix[i][j] != 0:
                stack.append([matrix[i][j], False])
            elif stack and stack[-1][1] == False and stack[-1][0] == matrix[i][j]:
                latest, _ = stack.pop()
                stack.append([matrix[i][j] + latest, True])
            elif stack and matrix[i][j] != 0:
                stack.append([matrix[i][j], False])

        for j in range(len(stack)):
            if way == 1:
                new_matrix[i][j] = stack[j][0]
            elif way == 2:
                new_matrix[i][N-1-j] = stack[j][0]

    return new_matrix

def get_max(matrix):
    return max([max(q) for q in matrix])

ways = [list('ulrd') for _ in range(5)]

answer = 0
# 5번 모든 경우의 수 돌면서 이동시켜 봄.
for way in list(product(*ways)):
    new_matrix = matrix
    for each_way in way:
        if each_way == 'u':
            new_matrix = up_down_movement(1, new_matrix)
        elif each_way == 'd':
            new_matrix = up_down_movement(2, new_matrix)
        elif each_way == 'l':
            new_matrix = left_right_movement(1, new_matrix)
        elif each_way == 'r':
            new_matrix = left_right_movement(2, new_matrix)
        answer = max(answer, get_max(new_matrix))

print(answer)