백준 1890번 - 점프

점프 문제 바로 가기

풀이 날짜: 2026-01-12

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

n = int(input())
dp = [[0]*n for _ in range(n)]
dp[0][0] = 1

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

for i in range(n):
    for j in range(n):
        if dp[i][j] == 0:
            continue
        jump = graph[i][j]
        if jump == 0:
            continue

        ni = i + jump
        nj = j + jump

        if ni < n:
            dp[ni][j] +=dp[i][j]
        if nj < n:
            dp[i][nj] += dp[i][j]
print(dp[n-1][n-1])

문제 접근

“최소 횟수”나 “최단 거리”가 아니라, 도착 지점까지 갈 수 있는 모든 경로의 개수를 구하는 것이다. 각 칸에는 점프할 수 있는 거리만 주어지고, 그만큼 오른쪽이나 아래로만 이동할 수 있다. 즉, 한 칸씩 이동하는 일반적인 BFS/DFS 문제가 아니라, 경로의 수를 누적해서 세는 DP문제였다는 것을 먼저 파악해야 했다.

DP 정의

dp[i][j] = (0,0)에서 (i,j)까지 도달할 수 있는 경로의 개수

이렇게 정의하면,

시작점 (0,0)은 도달하는 방법이 1개이다.→ dp[0][0] = 1
이후 칸들은 이전 칸들의 결과를 더해 받는 구조이다.

헷갈렸던 점 정리

왜 dp를 0으로 초기화했는가.

dp 배열은 “아직 도달하지 못한 칸”을 표현하기 위해 전부 0으로 초기화했다. 경로가 존재하는 칸만 값이 양수가 되고, 도달 불가능한 칸은 계속 0으로 남는다.

jump == 0 을 반드시 처리해야 하는 이유

문제 조건상 (n-1, n-1) 도착 칸의 값은 항상 0이다.
이 칸은 종착점이지 출발점이 아니므로, 여기서 또 이동을 시도하면 안 된다.

Vienna sausage