[Graph, DP] 점프 - 백준

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

1890번: 점프

 

많이 익숙한 그래프 maps 탐색 유형이다

우선 maps의 경로를 짤 때 유형은 꼭 익혀 놓도록 하자! 유사 유형들과 같다

 

우선 최종 구현 코드는 다음과 같다.

N = int(input())
maps = {}

for i in range(N) :
    maps[i] = [int(x) for x in input().split()]
global cnt
cnt = 0

def search(row, col, memo={}) :
    global cnt
    if (row, col) in memo :
        return memo[(row,col)]
    if (row, col) == (N-1, N-1) :
        cnt += 1
        return cnt
    if maps[row][col] == 0 :
        return cnt
    a = False; b = False
    cnt1 = 0; cnt2 = 0;
    if row != N-1 :
        a = True
    if col != N-1 :
        b = True
    if a :
        if row + maps[row][col] <= N-1 :
            cnt1 = search(row + maps[row][col], col, memo)
            cnt = 0
    if b :
        if col + maps[row][col] <= N-1 :
            cnt2 = search(row, col + maps[row][col], memo)
            cnt = 0
    memo[(row, col)] = cnt1+cnt2 
    return cnt1+cnt2

result = 0
result = search(0, 0)
print(result)

 

여기서 중요한 점은 문제를 똑바로 이해해야 하는 부분과

세밀한 코드를 진행해 주어야 한다.

가령

이런식으로 좌표를 업데이트한 값은 recursive 함수에 넣어주고

나머지는 그대로 두어야 하는데

주석 표시처럼 다음처럼 쓰게 되면 문제가 된다

 

그리고 0이 종점에만 있는 것이 아니라

중간에 있을 수도 있음을 기억하자

즉 다음 그림처럼 말이다

 

비교적 쉽게 통과했지만 유사 문제를 통해 계속 연습하자