[동적계획법/DP] 백준 1890 점프 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1890번: 점프

 

 

 

2. 문제 풀이

 주어진 게임판의 적힌 숫자만큼 오른쪽 혹은 아래로 이동하여, 최우측 하단에 도착하는 경우의 수를 찾는 문제입니다.

 

 

 

3. 코드

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

# 입력
n = int(input())
board = []

for _ in range(n):
    board.append(list(map(int, input().split())))

# BFS
queue = deque([(0, 0)])
cnt = 0
while queue:
    x, y = queue.popleft()
    dist = board[x][y]

    # 도착
    if dist == 0:
        cnt += 1
        continue

    # 오른쪽 이동
    nx = x + dist
    if 0 <= nx < n:
        queue.append((nx, y))

    # 왼쪽 이동
    ny = y + dist
    if 0 <= ny < n:
        queue.append((x, ny))
print(cnt)

 이동하는 경로 찾기라서 맨 처음에는 BFS로 접근했습니다.

 하지만 해당 접근방식은 이미 탐색한 곳도 계속 반복적으로 탐색하므로 메모리 초과가 났습니다.

 (일부 같은 경로라도 다른 시작점에서 갈 수 있어서, visited 테이블 운용 X)

 (굳이 하려면 최우측 하단 도착 시, 해당 경로를 다르게 표시해서 다시 탐색하는 일이 없도록 해야 함)

 

 

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

# 입력
n = int(input())
board = []

for _ in range(n):
    board.append(list(map(int, input().split())))

# DP
dp = [[0]*n for _ in range(n)]
dp[0][0] = 1

for x in range(n):
    for y in range(n):
        # 도착
        if x == n-1 and y == n-1:
            print(dp[x][y])
            exit()

        dist = board[x][y]
        # 아래로 이동
        nx = x + dist
        if nx < n:
            dp[nx][y] += dp[x][y]

        # 오른쪽 이동
        ny = y + dist
        if ny < n:
            dp[x][ny] += dp[x][y]

 그보다는 DP를 통해 해결하는 방법이 쉽습니다.

 2차원 배열이 쓰인 동적계획법으로, (0, 0)부터 (n, n)까지 모두 순차적으로 탐방합니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)