[Python/BFS] BOJ-12100 2048 (Easy)

까다롭다.

판이 주어지고, 각 스텝마다 판 전체의 값이 달라진다.

움직이는 방향이 4가지이므로 , 바뀌는 판도 4가지다.

from collections import deque
from copy import deepcopy

# 상 하 좌 우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def move(board, di):
    # 블록이 합쳐질 수 있는지를 bool타입으로 담는다.
    merged = [[True]*n for _ in range(n)]
    
    # 움직이는 방향에 따라 반복문의 진행방향이 다르다.
    # 위 또는 왼쪽으로 이동하는경우
    if di in [0,2]:
        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):
            x,y = i,j
            if board[x][y] == 0 :
                continue
            value = board[x][y]
            board[x][y] = 0
            nx, ny = x + dx[di], y + dy[di]
            while True :
                if nx < 0 or nx >=n or ny < 0 or ny >=n :
                    break # 판에서 벗어남
                # 다음 좌표가 비어있을 경우, 현재 좌표를 이동
                if board[nx][ny] == 0 :
                    x,y = nx,ny
                    nx,ny = x + dx[di], y+dy[di]
                # 다음 좌표와 같은 값인 경우, 하나의 좌표로 합친다.
                elif board[nx][ny] == value and merged[nx][ny] :
                    x,y = nx,ny
                    merged[x][y] = False
                    break
                # 다음 이동 좌표가 비어있지도 않고, 같은 값도 아닌경우 움직임종료
                else :
                    break
            board[x][y] += value
    return board

def bfs(board) :
    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):
                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))

회고

이런 문제는 늘 발목을 잡는다. input을 늘려서 다양한 각도로 접근해보자.