[백준/1890/파이썬] 점프

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

1890번: 점프

Problem

• N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.
• 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

조건

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

SOL

경로를 찾는 BFS/DFS 문제랑 비슷하게 생겼다. 하지만, 이 문제는 완전탐사의 일부분인 BFS/DFS로 풀지 못한다.

• 경로를 찾는 문제여서, BFS/DFS를 써버리면, 안되는 유형 중 하나이다. 문제를 생각해주면, 시작점은 (0,0)으로 고정되어있지만, 우리가 흔히 보는 4가지 방향으로 탐사하는거나, 그런 조건은 하나도 없음.
• 완전탐색을 한다면,각각의 시작점에서 2가지 방향을 다 가봐야하고, 결국 끝에 도달하지 못하면, 다시 그 이전 과정으로 돌아와서, 다시 길을 가야하므로, O(2^n)꼴로 구현을 해야할 것이다.
• 그래서, 이 문제는 재귀로 구현한다면, 메모이제이션을 첨가해서 구현하거나, DP table로 푸는 전형적인 DP 문제가 되버린다. (사실, DFS + cache를 자연스럽게 떠올렸다면, 그냥 그대로 풀어도된다!)

import sys
input = sys.stdin.readline

N = int(input().rstrip())

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 DP[i][j] !=0 and board[i][j] !=0:
            if j+board[i][j]<N:
                DP[i][j+board[i][j]] += DP[i][j] 
            if i+board[i][j]<N:
                DP[i+board[i][j]][j] +=DP[i][j]

#print(DP)
print(DP[N-1][N-1])