[백준] 2048

2048 (Easy)

2048 (Easy)

코드

import sys
from collections import deque

def bfs(board, max):

    count = 0

    q = deque()
    q.append((board, count))

    while q:
        brd, cnt = q.popleft()
        if cnt >= 5:
            return print(max)
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        for i in range(n):
            for j in range(n):
                brd[i][j][1] = False

        for i in range(4):
            copy_board = [item[:] for item in brd]
            if i == 0:
            # 위로 밀 때
                for j in range(1, n):
                    for k in range(n):
                        a, b = j, k
                        if copy_board[a][b][0] != 0:
                            if a + dx[i] >= 0:
                                while copy_board[a + dx[i]][b + dy[i]][0] == 0:
                                    copy_board[a + dx[i]][b + dy[i]] = copy_board[a][b]
                                    copy_board[a][b] = [0, False]
                                    a += dx[i]
                                    b += dy[i]
                                    if a + dx[i] < 0:
                                        break
                                if a + dx[i] >= 0:
                                    if copy_board[a + dx[i]][b + dy[i]] == copy_board[a][b] and copy_board[a][b][0] != 0:
                                        if not copy_board[a + dx[i]][b + dy[i]][1]:
                                            if max < copy_board[a + dx[i]][b + dy[i]][0] * 2:
                                                max = copy_board[a + dx[i]][b + dy[i]][0] * 2
                                            copy_board[a + dx[i]][b + dy[i]] = [copy_board[a + dx[i]][b + dy[i]][0] * 2, True]
                                            copy_board[a][b] = [0, False]
                if brd != copy_board:
                    q.append((copy_board, cnt + 1))

            elif i == 1:
                # 아래로 밀 때
                for j in range(n - 1, -1, -1):
                    for k in range(n):
                        a, b = j, k
                        if copy_board[a][b][0] != 0:
                            if a + dx[i] < n:
                                while copy_board[a + dx[i]][b + dy[i]][0] == 0:
                                    copy_board[a + dx[i]][b + dy[i]] = copy_board[a][b]
                                    copy_board[a][b] = [0, False]
                                    a += dx[i]
                                    b += dy[i]
                                    if a + dx[i] >= n:
                                        break
                                if a + dx[i] < n:
                                    if copy_board[a + dx[i]][b + dy[i]] == copy_board[a][b] and copy_board[a][b][0] != 0:
                                        if not copy_board[a + dx[i]][b + dy[i]][1]:
                                            if max < copy_board[a + dx[i]][b + dy[i]][0] * 2:
                                                max = copy_board[a + dx[i]][b + dy[i]][0] * 2
                                            copy_board[a + dx[i]][b + dy[i]] = [copy_board[a + dx[i]][b + dy[i]][0] * 2, True]
                                            copy_board[a][b] = [0, False]
                if brd != copy_board:
                    q.append((copy_board, cnt + 1))

            elif i == 2:
                # 좌로 밀 때
                for j in range(n):
                    for k in range(1, n):
                        a, b = j, k
                        if copy_board[a][b][0] != 0:
                            if b + dy[i] >= 0:
                                while copy_board[a + dx[i]][b + dy[i]][0] == 0:
                                    copy_board[a + dx[i]][b + dy[i]] = copy_board[a][b]
                                    copy_board[a][b] = [0, False]
                                    a += dx[i]
                                    b += dy[i]
                                    if b + dy[i] < 0:
                                        break
                                if b + dy[i] >= 0:
                                    if copy_board[a + dx[i]][b + dy[i]] == copy_board[a][b] and copy_board[a][b][0] != 0:
                                        if not copy_board[a + dx[i]][b + dy[i]][1]:
                                            if max < copy_board[a + dx[i]][b + dy[i]][0] * 2:
                                                max = copy_board[a + dx[i]][b + dy[i]][0] * 2
                                            copy_board[a + dx[i]][b + dy[i]] = [copy_board[a + dx[i]][b + dy[i]][0] * 2, True]
                                            copy_board[a][b] = [0, False]
                if brd != copy_board:
                    q.append((copy_board, cnt + 1))

            else:
                # 우로 밀 때
                for j in range(n):
                    for k in range(n - 1, -1, -1):
                        a, b = j, k
                        if copy_board[a][b][0] != 0:
                            if b + dy[i] < n:
                                while copy_board[a + dx[i]][b + dy[i]][0] == 0:
                                    copy_board[a + dx[i]][b + dy[i]] = copy_board[a][b]
                                    copy_board[a][b] = [0, False]
                                    a += dx[i]
                                    b += dy[i]
                                    if b + dy[i] >= n:
                                        break
                                if b + dy[i] < n:
                                    if copy_board[a + dx[i]][b + dy[i]] == copy_board[a][b] and copy_board[a][b][0] != 0:
                                        if not copy_board[a + dx[i]][b + dy[i]][1]:
                                            if max < copy_board[a + dx[i]][b + dy[i]][0] * 2:
                                                max = copy_board[a + dx[i]][b + dy[i]][0] * 2
                                            copy_board[a + dx[i]][b + dy[i]] = [copy_board[a + dx[i]][b + dy[i]][0] * 2, True]
                                            copy_board[a][b] = [0, False]
                if brd != copy_board:
                    q.append((copy_board, cnt + 1))
    return print(max)

if __name__ == '__main__':
    n = int(sys.stdin.readline())

    board = []

    for i in range(n):
        board.append(list(map(int, sys.stdin.readline().split())))
    max = 0
    for i in range(n):
        for j in range(n):
            if max < board[i][j]:
                max = board[i][j]
            board[i][j] = [board[i][j], False]

    bfs(board, max)