백준 1890 점프

점프 (백준 1890)

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

맵을 이동하면서 정답을 찾는 문제이기에,
top - down의 방식을 이용하였다

DFS + DP의 방식을 적용하였고,
내용이 직관적이라 코드 자체는 금방 만들었다

다만,
해당 값이 ‘0’일 때, 도착인 것으로 처리되는 것이 아니라
‘오른쪽 아래’에 도착한 경우에만 ‘도착’으로 처리되기에
해당 부분에서 ‘로직’이 틀렸나 고민했지만,
이후 지문을 다시 잘 읽어보고 수정하였다

비슷한 유형이라고 문제를 대충 읽으면,
큰코 다칠수 있다

Code

import sys

sys.setrecursionlimit(10**8)

inp = sys.stdin.readline

n = int(inp().strip())

dp = [[0 for _ in range(n)]for _ in range(n)]
val = [list(map(int,inp().split())) for _ in range(n)]

def dfs(x,y)->int:
    if x == n-1 and y == n-1:
        return 1
    
    if val[x][y] == 0:
        return 0

    if dp[x][y] != 0:
        return dp[x][y]

    sum = 0
    for nx,ny in [(x+val[x][y],y),(x,y+val[x][y])]:
        if 0<= nx <n and 0 <=ny<n:
            sum += dfs(nx,ny)

    dp[x][y] = sum 

    return sum

print(dfs(0,0))

해결 아이디어

1. 오른쪽 아래에 도착하는 경우는,
   도착이므로 1을 반환한다
2. 0을 만나는 경우는 진행할 수 없으므로 0을 반환
   
3. dp에 이미 해당 부분에 대한 데이터가 있다면
   해당 데이터를 리턴한다
   (dp 테이블이 오른쪽 아래부터 점점 차오르는 방식이며,
   끝날 즈음엔 dp[0][0]에 총 횟수가 들어오도록 하였음)
   => DFS를 이용한 이유는 ‘이미’ 앞서 방문한 곳이라면
   dp값이 존재한다 판단하기 위하여
4. 오른쪽과 아래쪽을 탐색하며, 맵을 벗어나지 않는 경우,
   재귀를 돌리도록 한다
   이 때, sum 변수에 두 root의 경로 값을 더하도록 한다
5. sum을 dp[x][y]에 저장하고
   return 한다