[백준] 1890번 점프 파이썬 풀이

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

1890번: 점프

---

1. 접근 방식

• dfs로 접근하면 안 된다

시작점과 끝점이 명확한 그래프 문제처럼 보이지만, DFS로 풀면 시간 초과가 발생한다.

 

 

• bfs로도 접근하면 안 된다

(a - 1, b)에서 (a, b)를 방문하게 되는 경우와 (a, b - 4)에서 (a, b)를 방문하게 되는 경우는 서로 다르게 취급되어야 한다.

그러나 bfs에서 각 노드의 방문 여부를 나타내는 visited라는 배열은 (a - 1, b)로부터 (a, b)를 방문하든, (a, b - 4)로부터 (a, b)를 방문하든, 두 경우를 서로 다르게 취급하지 못 한다. 그냥 방문했다는 사실밖에 나타내지 못 한다.

 

 

• 2차원 배열 db로 접근하자

노드의 위치 정보를 나타내려면 2가지 인덱스가 필요하므로, dp 배열 역시 모두 0으로 이뤄진 2차원 배열로 초기화해야 한다. dp는 특정 노드에 접근할 수 있는 경로의 개수를 담는 용도이다. 시작 지점인 (0, 0)은 1로 초기화하자. 시작 지점으로의 경로 개수는 반드시 1개밖에 없기 때문이다.

게임판의 모든 칸을 2중 반복문으로 순회한다. 반복문 종료 조건은 행을 나타내는 i와 열을 나타내는 j가 마지막 칸을 가리킬 때이다. 오른쪽과 왼쪽으로 점프할 수 있는 만큼 이동하면서 모든 경로의 개수를 구하면 된다.

 

 

 

2. 정답 코드

import sys
input = sys.stdin.readline


def solve(n):
    for i in range(n):
        for j in range(n):
            if i == n - 1 and j == n - 1:
                return dp[i][j]

            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]


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

print(solve(N))