[BaekJoon] 12100 2048 (Easy)

yunan·2020년 10월 10일
0
post-thumbnail

🔦 문제 링크

✍️ 풀이


두가지 의문이 있었다.

  • 어떻게 배열의 정보를 유지할 것인가?
  • 모든 정보를 보관하면 dfs, bfs 시 메모리가 너무 많아지지 않을까?

5번만 진행하면 되기 때문에 dfs를 하면 최대 5개의 배열 복사본이 생긴다.
그렇기 때문에 메모리 초과를 걱정하지 않아도 된다.

🤔 그럼 어떻게 각 행과 열을 합칠 것인가?

  • 각 행 또는 열의 값을 큐에 담는다. (담은 값은 0으로 변환)
  • 이후 큐에 있는 값을 꺼내 없으면 넣고 같으면 곱하고 다르면 다음에 넣는 과정에 반복한다.

🛠 코드


from collections import deque
from sys import stdin

mx = -1
n = int(input())
a = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
q = deque()


def get(i, j):
    if a[i][j]:
        q.append(a[i][j])
        a[i][j] = 0


def merge(i, j, di, dj):
    while q:
        val = q.popleft()
        if not a[i][j]:
            a[i][j] = val
            # 다음 원소는 아직들어가지 않았으므로 a[i+di][j+dj] == 0이다..
        elif a[i][j] == val:
            a[i][j] = val * 2
            i, j = i + di, j + dj
        else:
            i += di
            j += dj
            a[i][j] = val


def move(k):
    if k == 0:  # Up 이면 위로 숫자를 모으면서 점점 밑으로 내려오는 구조이다.
        for j in range(n):
            for i in range(n):
                get(i, j)  # 큐에 블럭을 담는 함수
            merge(0, j, 1, 0)  # 큐에 담은 블럭을 합치는 함수
    elif k == 1:  # down
        for j in range(n):
            for i in range(n-1, -1, -1): # 순서도 반대가 된다.
                get(i, j)
            merge(n - 1, j, -1, 0)
    elif k == 2:  # left
        for i in range(n):
            for j in range(n):
                get(i, j)
            merge(i, 0, 0, 1)
    elif k == 3:  # right
        for i in range(n):
            for j in range(n-1, -1, -1):
                get(i, j)
            merge(i, n - 1, 0, -1)


def dfs(index):
    global mx, a
    if index == 5:
        for i in range(n):
            mx = max(mx, max(a[i]))
        return
    b = [tmp[:] for tmp in a] # 복사 시 사용
    for i in range(4):
        move(i)
        dfs(index + 1)
        a = [tmp[:] for tmp in b]


dfs(0)
print(mx)

📝 정리


  • 구현력이 중요한 문제였다.
  • 푸는 방법이 떠올라도 구현하지 못하면 의미가 없다.
  • 많은 문제를 풀고 참고하는 것이 구현력에 도움이 될 것 같다.

🎈 참고


rebas님 블로그

profile
Go Go

0개의 댓글