[Python] 백준 1890번 - 점프 (실버 1)

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

1890번: 점프

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 다이나믹 프로그래밍

 

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

---

처음엔 bfs 문제인 줄 알고 큐에 담아서 풀었다.

 

문제의 결과는 '메모리 초과' 생각해보니

 

모든 값이 1로만 이루어져 있으면 굉장히 많은 수의 큐가 담길 것으로 메모리가 초과될 만도 하다.

 

그래서 다시 찾은 방법은 DP로 푸는 방법이다.

 

앞선 경우의 수를 더하면서 값을 채우는 것이다.

 

import sys
input = sys.stdin.readline

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

visited = [[0 for _ in range(n)] for _ in range(n)]
visited[0][0] = 1
for i in range(n):
    for j in range(n):
        if visited[i][j] == 0 or (i == n-1 and j == n-1):
            continue
        jump = data[i][j]
        if i+jump < n:
            visited[i+jump][j] += visited[i][j]
        if j + jump < n:
            visited[i][j+jump] += visited[i][j]
            
print(visited[n-1][n-1])
# for i in range(n):
#     print(visited[i])

각각 왼쪽에서 오는 값, 오른쪽에서 오는 값을 순차적으로 순환한다.

 

2중 for문으로 푸는 것이 가능한 이유는 방향이 아래, 오른쪽 둘 뿐이기 때문에

 

반복문으로 순회하면서 찾는 것이 가능하다.