[백준/알고리즘] #1890:점프 [파이썬(python)/DFS/BFS]

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

1890번: 점프

처음에 문제를 이해 못해서... 결국 예제 하나하나 그려보고나서야 이해했다...ㅎㅎ

 

예제 따라 저렇게 3가지 경우의 수가 나오므로 답이 3이다.

 

간단한 DFS/BFS 정석적인 문제 같은데 또 새로운 풀이의 DFS/BFS 문제여서 고민했다. (많이 많이 풀어보는 수 밖에......)

 

갈 수 있는 방향이 목표지점까지로만 갈 수 있도록 제한되어있다. 사이클은 안된다.

 

오른쪽과 아래쪽으로만 움직일 수 있으므로 N*N 판 반복문에서 현재좌표를 이용해 visited배열에 카운트하면 된다. 

 

파이썬 코드

#1890_점프
import sys
input = sys.stdin.readline

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

visited = [[0]*N for _ in range(N)]
visited[0][0]=1

for i in range(N):
    for j in range(N):
        if i==N-1 and j==N-1: #(N,N) 종착 
            print(visited[i][j])
            break
        cur = game[i][j]
        print(cur)
        if j+cur < N: #right
            visited[i][j+cur] += visited[i][j]
        if i+cur < N: #down
            visited[i+cur][j] += visited[i][j]