[python] 백준 1890번: 점프(DP)

# 1890 점프

https://www.acmicpc.net/problem/1890

1890번: 점프

⭐ 코드

import sys
input = sys.stdin.readline
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        
        if i == N-1 and j == N-1:
            print(dp[i][j]) 
            break
        
        jump = board[i][j]

        if i + jump < N:
            dp[i + jump][j] += dp[i][j]
        
        if j + jump < N:
            dp[i][j + jump] += dp[i][j]

📝 풀이

처음에는 BFS나 DFS로 구해보려고 했다. 정답들을 살펴보니까 못 구하는건 아닌데 코드를 작성하기가 어려웠고, 결국 DP로 접근하게 됐다. 

 

맨 처음으로 생각해야 될 점이 jump의 범위 설정이다. 목적지에 가기까지 jump 범위가 N의 값을 벗어나면 안되기 때문에 범위 설정을 잘 해줘야 하고, 범위 내에 있으면 그전 좌표까지 이동 가능한 값을 더한다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline
N = int(input())

board = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]
dp[0][0] = 1

board와 dp 리스트를 생성해주고 0,0에서 시작하므로 초기 값(dp[0][0])을 1로 설정해준다.

# 반복문으로 그래프의 좌표 탐색
for i in range(N):
    for j in range(N):
        
        # 마지막 값 출력
        if i == N-1 and j == N-1:
            print(dp[i][j]) # 마지막 값
            break
        
        jump = board[i][j] # 점프 값

        # 아래쪽 방향
        if i + jump < N:
            dp[i + jump][j] += dp[i][j]
        
        # 오른쪽 방향
        if j + jump < N:
            dp[i][j + jump] += dp[i][j]

# dp
# [
# [1, 0, 1, 0], 
# [0, 0, 0, 0], 
# [1, 1, 0, 1], 
# [1, 0, 1, 3]
# ]

이중 반복문으로 board를 탐색해주면서 board[i][j]의 값, 즉 jump값을 저장시켜준다. 아래쪽과 오른쪽을 탐색하면서 범위 내에 있다면 점프한 위치(dp[i + jump][j]에 값을 더해준다. 반복문을 다 돌게 되면 위와 같이 dp리스트가 생성되게 되고 마지막 값을 출력시켜주면 된다.