[Python] 백준 12100번: 2048(Easy)

dfs vs bfs

백준 13460번: 구슬 탈출 2 풀이

• 구슬탈출2와 비슷한 점
  • 최대 이동 횟수가 정해져 있다.

• 구슬탈출2와 다른점
  • 구슬탈출2는 이동하는 구슬이 2개였지만, 이 문제에서는 이동하는 블럭이 최대 n*n개이다.
    따라서 이동 방향에 따라 다른 순서로 블럭을 하나씩 이동시켜야 한다.
  • 구슬탈출2는 구슬 탈출이 발생한 순간 횟수 출력 후 종료 가능하지만, 이 문제에서는 5번까지 가봐야 가장 큰 블록을 확신할 수 있음 ⇒ 완전탐색

로직

아래 두가지 포인트에 유의하여 로직을 작성했습니다.

1. 이동 방향에 따라 x와 y의 range가 달라짐
2. 이미 integrated된 위치를 또 합치지 않아야 함

코드

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
range_x = [range(1, n), range(n - 2, -1, -1), range(n), range(n)]
range_y = [range(n), range(n), range(1, n), range(n - 2, -1, -1)]


def deepcopy(list):
    nlist = [[0] * n for _ in range(n)]
    for x in range(n):
        for y in range(n):
            nlist[x][y] = list[x][y]
    return nlist


def move(blocks, i):
    integrated = []
    for x in range_x[i]:
        for y in range_y[i]:
            if blocks[x][y] != 0:
                block = blocks[x][y]
                blocks[x][y] = 0
                nx = x
                ny = y
                while True:
                    nx += dx[i]
                    ny += dy[i]
                    if not (0 <= nx < n and 0 <= ny < n):
                        break
                    if blocks[nx][ny] == block and (nx, ny) not in integrated:
                        integrated.append((nx, ny))
                        nx += dx[i]
                        ny += dy[i]
                        break
                    elif blocks[nx][ny] != 0:
                        break
                nx -= dx[i]
                ny -= dy[i]
                blocks[nx][ny] += block


def dfs(board, i):
    global ans
    nboard = deepcopy(board)
    move(nboard, i)

    if len(s) == 5:
        ans = max(ans, max([max(b) for b in nboard]))
        return

    for i in range(4):
        s.append(i)
        dfs(nboard, i)
        s.pop()


s = []
ans = 0
for i in range(4):
    s.append(i)
    dfs(board, i)
    s.pop()

print(ans)

참고

반례를 모아놓은 블로그가 있어 첨부합니다.
반례 확인하러 가기