[BOJ] 12100. 2048 (Easy)

문제

2048 (Easy) (https://www.acmicpc.net/problem/2048)

풀이

1. 초기 접근

• 문제조건 해석

  • 판이 주어지고, 각 스텝마다 판 전체의 값이 달라진다.
  • 움직이는 방향은 4가지 이므로, 바뀌는 판도 4가지 경우가 생긴다.
  • 특정 스텝에서 멈추고, 가장 큰 값을 반환해야 한다.
    • BFS 문제다.

• 알고리즘

  • 전체적인 BFS 문제, 바뀌는 것은 전체 판이니, BFS queue 에 전체 판을 넣어주면 된다.
  • 한 번에 4가지 경우의 판이 생기고, 총 5번까지 해야하니, 최대 경우의 수는 4^5 = 1024개다.
  • 각 방향에 대하여 움직이는게 좀 까다로운데, 이를 별도의 함수 move(board, di) 로 두자.
    • 먼저 이전의 판 board 와 움직이는 방향 di 를 넘겨받아, 움직임이 완료된 판을 반환하는 게 이 함수의 목표다.
    • 움직이는 방향에 따라, 업데이트 해줘야하는 좌표의 순서가 다른데,
      위, 또는 왼쪽으로 움직이는 경우, 반복문의 방향은 왼쪽 위에서 오른쪽 아래 방향이다. (일반적인 반복문)
      아래, 또는 오른쪽으로 이동하는 경우, 위 경우의 반대방향으로 업데이트를 해줘야 한다.
    • 이동하다가 같은 값을 발견해 합쳐야 하는 경우, 합칠 수 있는지 여부를 can_merge 로 판단한다.

• 코드

from collections import deque
from copy import deepcopy

dxs = [-1, 0, 1, 0]
dys = [0, 1, 0, -1]

def move(board, di):
    # can_merged[i][j] 는 (i, j)번째 블록이 합쳐질 수 있는지를 bool 타입으로 담는다.
    can_merged = [[True] * n for _ in range(n)]

    # 움직이는 방향에 따라, 반복문의 진행방향이 다르다.
    # 위 또는 왼쪽으로 이동하는 경우
    if di in [0, 3]:
        start_idx, end_idx, step = 0, n, 1

    # 아래 또는 오른쪽으로 이동하는 경우
    else:
        start_idx, end_idx, step = n-1, -1, -1

    # 현재 판의 모든 좌표를 탐색하며, 움직임이 필요한 값들은 움직인다.
    for i in range(start_idx, end_idx, step):
        for j in range(start_idx, end_idx, step):
            if board[i][j] == 0:
                continue

            x, y = i, j
            value = board[x][y]
            board[x][y] = 0
            nx, ny = x + dxs[di], y + dys[di]
            while True:
                # 범위 체크
                if nx < 0 or nx >= n or ny < 0 or ny >= n:
                    break

                # 다음 이동 좌표(nx, ny)가 비어있는 경우, 현재 좌표(x, y)를 이동.
                if board[nx][ny] == 0:
                    x, y = nx, ny
                    nx, ny = x + dxs[di], y + dys[di]

                # 다음 이동 좌표에 현재 이동하는 숫자와 같은 값인 경우, 해당 좌표를 합쳐진 상태로 바꾼다.
                elif board[nx][ny] == value and can_merged[nx][ny]:
                    x, y = nx, ny
                    can_merged[x][y] = False
                    break

                # 다음 이동 좌표가 비어있지도 않고, 같은 값도 아닌 경우, 움직임 종료.
                else:
                    break
            board[x][y] = board[x][y] + value

    return board

def bfs(board):
    """ 알고리즘 간략 설명
    1. bfs queue 에다가, 각 스텝에 따른 판 전체(board)를 집어넣는다.
    2. queue 에서 판을 하나씩 빼와, 4가지 방향으로 움직인 후의 판을 queue에 집어 넣는다.
    3. 스텝이 5번 째가 되었을 때, bfs 를 강제 종료.
    """
    q = deque([board])
    max_value = -1
    step = 0

    while q:
        size = len(q)

        for _ in range(size):
            board = q.popleft()

            for di in range(4):
                # 새로운 판을 만들어야 하므로, 반드시 deepcopy 해야한다!
                next_board = move(deepcopy(board), di)
                q.append(next_board)

                # 새로 만든 판에서 가장 큰 값을 조사한다.
                for i in range(n):
                    for j in range(n):
                        if next_board[i][j] > max_value:
                            max_value = next_board[i][j]      

        step += 1

        # 다섯 번째 스텝일 때, 지금까지 가장 큰 값을 반환한다.
        if step == 5:
            return max_value

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

print(bfs(board))

유의 사항

• 전체적인 BFS 꼴에, 움직이는 것만 좀 더 신경써줘야 하는 문제다.
• 이런류의 문제에서는 흔히, 현 스텝에서, 현재 좌표 (x, y) 값의 움직임이, 다른 좌표 값이 움직일 때 영향을 주냐 안주느냐에 따라, 일괄적으로 업데이트 해야하느냐, 아니냐로 갈리곤 한다.
  • 이 문제는 전자다. 영향을 준다. 그래서 반복문의 방향에 신경써야 한다.
• 파이썬에서 변수에 값이나, 또다른 변수(객체) 를 할당할 때, memory reference 가 된다는 것을 늘 명심해야 한다.
  • 현재 변수, 객체를 그대로 카피하되, 원본에 영향을 안주게 작업하려면 deep copy를 해야한다.
  • 참고로, 자료구조에서 지원하는 .copy 는 shallow copy 이다.
  • 매우매우 중요하므로, 헷갈리면 아래 링크 꼭 참조하자.

Understanding dict.copy() - shallow or deep?

https://stackoverflow.com/questions/3975376/understanding-dict-copy-shallow-or-deep>