[2] boj12100 - 2048 (Easy)

[robert-min]

문제 추천 이유!!

• 시뮬레이션 문제
• 재귀 탐색하는 과정에 이전 결과를 저장해서 다시 사용하는 부분이 중요!!

문제 링크

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

*작성가이드 입니다.

1. 작성자가 먼저 문제를 풀어봅니다.
2. 문제를 풀고나서 난이도를 설정합니다.

• 1 : 30분 이내로 손 쉽게 풀 수 있음
• 2 : 1시간 이내로 고민하면 풀 수 있음
• 3 : 1시간 이상 걸리거나 어려움

3. Coding test Basic template을 사용하여 이슈를 생성합니다.

• 제목은 : [난이도] 문제명으로 작성합니다.
• 내용은 : 문제 링크만 추가하세요
• 문제 사이트를 label로 추가해주세요. 기본값은 백준

4. 문제 풀이는 이슈의 코멘트로 추가해주세요

• 풀이에 걸린 시간, 풀이 유형, 방식은 간단하게
• 문제를 풀고나서 스스로 풀이 또는 오답노트를 정리하는 느낌으로!!

5. 다른 사람에게 채팅으로 직접 문제를 추천하세요.

• 디스코드 채널을 통해 다른 모임원에게 문제를 추천
• 해당 모임원은 문제를 풀고 코멘트를 통해 추가로 공유하기!!

---

아래는 comment 템플릿입니다.(복사해서 사용)

⏰ 소요 시간 : 
🗂️ 유형 :

🖌️ 문제 풀이
- 

[robert-min]

⏰ 소요 시간 : 1시간
🗂️ 유형 : 시뮬레이션

🖌️ 문제 풀이

• 중요 팁!!
  • 아래 상황처럼 재귀로 탐색하는 과정에서 이전 matrix 값을 활용해야할 때, 별도의 변수로 저장!!
  • deepcopy와는 다른 방식으로 활용

# 방향 바꾸기 전 보드를 기억
m = [x[:] for  x in matrix]

for k in range(4):
    move(k)
    solve(cnt+1)
    matrix = [x[:] for x in m]

• 이동하는 부분은 여러 방식이 있어 아래처럼 빡구현해도 문제는 없음

def move(dir, x, y):
    global matrix
    if dir == 0 and x > 0 and matrix[x-1][y] == 0:    # 위로 이동
        matrix[x][y], matrix[x-1][y] = matrix[x-1][y], matrix[x][y]
        move(dir, x-1, y)
    elif dir == 1 and x < N - 1 and matrix[x+1][y] == 0:  # 아래로 이동
        matrix[x][y], matrix[x+1][y] = matrix[x+1][y], matrix[x][y]
        move(dir, x+1, y)
    elif dir == 2 and y > 0 and matrix[x][y-1] == 0:  # 왼쪽 이동
        matrix[x][y], matrix[x][y-1] = matrix[x][y-1], matrix[x][y]
        move(dir, x, y-1)
    elif dir == 3 and y < N - 1 and matrix[x][y+1] == 0:  # 오른쪽 이동
        matrix[x][y], matrix[x][y+1] = matrix[x][y+1], matrix[x][y]
        move(dir, x, y+1)


def union(dir, x, y):
    if dir == 0 and x > 0:
        if matrix[x-1][y] == matrix[x][y]:
            matrix[x-1][y] *= 2
            matrix[x][y] = 0
    elif dir == 1 and x < N - 1:
        if matrix[x+1][y] == matrix[x][y]:
            matrix[x+1][y] *= 2
            matrix[x][y] = 0
    elif dir == 2 and y > 0:
        if matrix[x][y-1] == matrix[x][y]:
            matrix[x][y-1] *= 2
            matrix[x][y] = 0
    elif dir == 3 and y < N - 1:
        if matrix[x][y+1] == matrix[x][y]:
            matrix[x][y+1] *= 2
            matrix[x][y] = 0

"""
Return : 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값
- 0 빈칸
- 상, 하, 좌, 우 이동
- 이동 방향에 있는 좌표부터 이동
- 이동 했을 때 같은 숫자가 있는 경우 결합

- up, down, left, right
  - 이동 방향에 좌표부터
- combine
"""
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))
answer = 0
Q = deque()


def get(i, j):
    if matrix[i][j]:
        Q.append(matrix[i][j])
        matrix[i][j] = 0


def merge(i, j, di, dj):
    while Q:
        x = Q.popleft()
        if not matrix[i][j]:    # 0이라면 그대로 놓음
            matrix[i][j] = x
        elif matrix[i][j] == x: # 값이 일치하면 2배 증가
            matrix[i][j] = x*2
            i, j = i+di, j+dj
        else:   # 값이 일치하지 않으면 
            i, j = i+di, j+dj
            matrix[i][j] = x


def move(k):
    # board[i][j]
    if k == 0: # 위로 이동, 블락들이 위로 모두 이동하면 row index는 0
        for j in range(N):
            for i in range(N):
                get(i, j)
            merge(0, j, 1, 0) # row index 1씩 증가하면서 아래쪽 블락들을 합쳐감
    elif k == 1: # 아래로 이동, 블락들이 아래로 모두 이동하면 row index는 n-1
        for j in range(N):
            for i in range(N-1, -1, -1):
                get(i, j)
            merge(N-1, j, -1, 0) # row 인덱스 1씩 감소하면서 위쪽들을 합쳐감
    elif k == 2: # 오른쪽으로 이동, column index는 0
        for i in range(N):
            for j in range(N):
                get(i, j)
            merge(i, 0, 0, 1) # column 인덱스 증가 오른쪽으로 이동
    else: # 왼쪽으로 이동, column index는 n-1
        for i in range(N):
            for j in range(N-1, -1, -1):
                get(i, j)
            merge(i, N-1, 0, -1) # column 인덱스 감소 왼쪽으로 이동


def solve(cnt):
    global answer, matrix
    if cnt == 5:
        for i in range(N):
            answer = max(answer, max(matrix[i]))
        return
    # 방향 바꾸기 전 보드를 기억
    m = [x[:] for  x in matrix]

    for k in range(4):
        move(k)
        solve(cnt+1)
        matrix = [x[:] for x in m]

solve(0)
print(answer)