[백준] 12100 - 2048 (Easy) (G2)

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

12100번: 2048 (Easy)

2048 게임의 타일 이동을 구현하는 문제이다.

최대 이동 횟수가 5회로 매우 작은데, 한번에 이동에서 선택할 수 있는 경우의 수가 '상하좌우' 4가지 이므로

모든 경우의 수가 4^5 = 1024 이다.

 

모든 경우의 수를 저장하기 위해서 각 경우마다 최대 20*20 사이즈 판을 순회해야 하므로

한 경우의 수당 연산횟수는 400이다.

 

1024 * 400 은 굳이 계산해보지 않아도 1억보다 작으므로, 1초안에 충분히 연산이 가능하다.

따라서 브루트포스 & 시뮬레이션으로 모든 경우의 수를 시뮬레이션하고

그 결과를 기존 최댓값과 비교하여 갱신해주면 된다.

 

이 문제의 난도가 높은 이유는 저 '시뮬레이션' 구현이 좀 복잡하기 때문일 것이다.

(개인적으로 이 구현이 골드2 씩이나 되나? 싶기도 한데, RPG Extreme 문제를 푼 이후로

그것보다 낮은 난도의 구현 문제에 대해 난도 판단이 둔감하게 된 것 같기도 하다...ㅋㅋㅋ)

---

나는 튜플을 이용해서 구현했다.

튜플은 얕은 복사가 되지 않기 때문이다.

 

이동 후 결과 구현은 last 변수와 line 리스트를 이용했다.

해당 라인에서 마지막으로 확인한 숫자를 체크한다.

 

2 2 4

 

첫 줄이 이렇게 되어있고, 이 상태의 판을 왼쪽으로 옮긴다고 해보자.

그럼 결과는

 

4 4 0

 

이 되어야 한다.

이를 구현하기 위해서 왼쪽으로 이동하는 경우,

한 가로줄씩 왼쪽부터 체크하여 결과값의 가로줄을 만들었다.

 

2 2 4

 

에서 맨 처음에 2 를 만나면, last 변수에 2를 저장하고. line 리스트에 2 를 push 한다.

그 이후 두번째 2를 만나면, last 변수에 저장된 값과 비교하여,

동일한 값일경우 기존 line 갑과 합치고 (line 리스트의 제일 오른쪽 값에 2를 더해준다) last 변수를 0으로 바꾼다.

이후 4를 만나면 last 변수가 0 이므로 4를 그냥 집어넣고 last 변수 값을 4로 바꾼다.

 

이렇게 last 변수를 활용한 이유는, 한번에 이동으로 숫자가 여러번 합쳐지지 않게 하기 위함이다.

만약 단순히 line 변수의 제일 오른쪽 값과 비교한다면

2 2 4

에서 

4 4 0

이 된 이후, 4 에 대해서 한번더 합쳐서

8 0 0

이라는 결과가 왼쪽 한번의 이동으로 나올 수도 있다.

 

지금은 왼쪽 이동이기 때문에 우리가 평소에 리스트를 순회하듯이 위에서 아래로, 왼쪽부터 오른쪽으로 순회했지만,

만약 오른쪽으로 이동시킨다면 리스트 순회 방향을 위에서 아래로(사실 이건 상관 없다.) 오른쪽부터 왼쪽으로 순회하면 된다.

아래로 이동시킨다면 왼쪽에서 오른쪽으로 (이것도 상관 없다.) 아래에서 위로 순회하고

위로 이동시킨다면 왼쪽에서 오른쪽으로 (방향은 상관 없음) 위에서 아래로 순회하여 위 과정을 반복하면 된다.

 

좌/우 로 이동하는 경우는 일반적인 리스트랑 자료형태가 비슷해서 그 line 자체를 바로 결과 리스트에 저장했지만,

상/하로 이동하는 경우, 그 결과 line을 바로 리스트에 저장할 수 없다.

따라서 미리 0 으로 초기화된 2차원 배열을 만들어두고, 세로로 값을 채워나갔다.

그리고 마지막에 최종 결과값 list를 모두 튜플로 바꾸어주었다.

(얕은 복사를 피하기 위함)

 

---

설명이 정말 길었지만, 코드를 보면 이해가 빠를 것으로 생각된다.

import sys
from collections import deque
input = sys.stdin.readline
TestMode = False

n = int(input())
board = tuple(tuple(map(int, input().split())) for _ in range(n))

def PrintBoard(board):
    if TestMode:
        for i in range(n):
            print(board[i])
    print()

############################################################
answer = 0

d = deque()
d.append((board, 0, tuple()))
while d:
    board, cnt, seq = d.popleft()
    # 만약 5번 이동이 끝난 결과물이 들어오면, 최댓값 찾고 종료
    if cnt == 5:
        for i in range(n):
            if TestMode and max(board[i]) > answer:
                print("answer board")
                PrintBoard(board)
                print(seq)
            answer = max(answer, max(board[i]))
        continue
    if TestMode:
        print("now board")
        PrintBoard(board)
    # UP
    up_result = [[0 for _ in range(n)] for _ in range(n)]
    for j in range(n):
        last, line = 0, []
        for i in range(n):
            if board[i][j] == 0:
                continue
            if last == 0:
                last = board[i][j]
                line.append(board[i][j])
            elif last == board[i][j]:
                last = 0
                line[-1] += board[i][j]
            else:
                last = board[i][j]
                line.append(board[i][j])
        line += ([0]*(n - len(line)))
        for k in range(n):
            up_result[k][j] = line[k]
    for k in range(n):
        up_result[k] = tuple(up_result[k])
    up_result = tuple(up_result)
    d.append((up_result, cnt + 1, seq + ('U',)))
    if TestMode:
        print("up result")
        PrintBoard(up_result)
    # Down
    down_result = [[0 for _ in range(n)] for _ in range(n)]
    for j in range(n):
        last, line = 0, []
        for i in range(n-1, -1, -1):
            if board[i][j] == 0:
                continue
            if last == 0:
                last = board[i][j]
                line.append(board[i][j])
            elif last == board[i][j]:
                last = 0
                line[-1] += board[i][j]
            else:
                last = board[i][j]
                line.append(board[i][j])
        line += ([0]*(n - len(line)))
        for k in range(n-1, -1, -1):
            down_result[k][j] = line[n-1-k]
    for k in range(n):
        down_result[k] = tuple(down_result[k])
    down_result = tuple(down_result)
    d.append((down_result, cnt + 1, seq + ('D',)))
    if TestMode:
        print("down result")
        PrintBoard(down_result)
    # Left
    left_result = []
    for i in range(n):
        last, line = 0, []
        for j in range(n):
            if board[i][j] == 0:
                continue
            if last == 0:
                last = board[i][j]
                line.append(board[i][j])
            elif last == board[i][j]:
                last = 0
                line[-1] += board[i][j]
            else:
                last = board[i][j]
                line.append(board[i][j])
        line += ([0]*(n - len(line)))
        left_result.append(tuple(line))
    left_result = tuple(left_result)
    d.append((left_result, cnt + 1, seq + ('L',)))
    if TestMode:
        print("left result")
        PrintBoard(left_result)
    # Right
    right_result = []
    for i in range(n):
        last, line = 0, deque()
        for j in range(n-1, -1, -1):
            if board[i][j] == 0:
                continue
            if last == 0:
                last = board[i][j]
                line.appendleft(board[i][j])
            elif last == board[i][j]:
                last = 0
                line[0] += board[i][j]
            else:
                last = board[i][j]
                line.appendleft(board[i][j])
        line = deque([0]*(n - len(line))) + line
        right_result.append(tuple(line))
    right_result = tuple(right_result)
    d.append((right_result, cnt + 1, seq + ('R',)))
    if TestMode:
        print("right_result")
        PrintBoard(right_result)
        print()

print(answer)

 

디버깅을 위해서 어떤 순서로 이동했는지, 매 이동 후 결과가 어떻게 나오는지 출력하도록 했는데,

TestMode 변수가 True 일때만 출력하므로 이를 False 로 바꾸면 백준 형식대로 답이 나오도록 했다.