백준: 1890 점프

문제

1890번: 점프

 

문제 풀이

 N X N 게임판이 주어질 때, 현재 경로에서 (0, 1), (1, 0)으로만 이동할 수 있다. 게임판에 주어진 숫자만큼 점프하여 이동하는 규칙이 적용될 때, (N, N)에 도달할 수 있는 경우의 수를 반환하는 문제이다. 이 문제는 단순히 보면 DFS나, BFS로 풀면 되겠지라고 생각되지만 N이 최대 100까지 커지므로 시간 초과가 발생하게 된다. 따라서 문제 분류와 같이 DP로 풀어야 한다.

 

 현재 위치의 점프할 수 있는 거리를 x, y축에 각각 더하여, N 보다 작다면 방문할 수 있는 경로이다. 이런식으로 현재 위치의 점프할 수 있는 거리가 0 (가장 오른쪽 아래 칸) 일 때까지 탐색하며, 가능한 경우의 수를 중첩한다.

 

코드

from sys import stdin


if __name__ == "__main__":
    n = int(stdin.readline())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    visited = [[0] * n for _ in range(n)]
    visited[0][0] = 1

    for x in range(n):
        for y in range(n):
            jump = graph[x][y]
            if not jump:
                break
            if x + jump < n:
                visited[x + jump][y] += visited[x][y]
            if y + jump < n:
                visited[x][y + jump] += visited[x][y]
                
    print(visited[-1][-1])