[Python] 백준 / silver / 1890번 (점프)

문제 링크 : https://www.acmicpc.net/problem/1890

BFS / DFS 알고리즘 문제,, 하지만 DP (다이나믹 프로그래밍) 알고리즘을 곁들인. 이거 풀면서 이게 왜 실버 문제지 ..? 절대 이해안됐다.

이 문제는 https://heyksw.tistory.com/8 에 정리했던 골드 DFS + DP 문제와 비슷한 문제다.

이 문제는 DFS 로만 푼다면 대략 최대 O(2^100) time 이 소요되어 효율성 테스트를 통과할 수 없고 반드시 다이나믹 프로그래밍을 해야한다.

dp[x][y] == (x,y)에서 (도착점)에 갈 수 있는 경로 수를 담아내는 로직 자체가 쉽지 않다.

처음에 푼 정답 코드

import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

direction = [(1, 0), (0, 1)]    # 하 우
dp = [[-1]*N for _ in range(N)]

def dfs(x, y):
    if x == N-1 and y == N-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 0
        for d in direction:
            nx = x + d[0] * graph[x][y]
            ny = y + d[1] * graph[x][y]
            if 0 <= nx < N and 0 <= ny < N:
                dp[x][y] += dfs(nx, ny)
    return dp[x][y]

print(dfs(0, 0))

아직 dfs 탐색이 이뤄지지 않은 좌표는 dp값으로 -1을 담고, 도착점에서는 1을 return한다. dp[x][y] += dfs(nx, ny)로 Top-Down 느낌의 다이나믹 프로그래밍을 해나간다. (dp += 재귀함수) 꼴이기 때문에 모든 재귀함수는 반드시 값을 return 해야한다. 코드 짜면서 dfs 함수 마지막에 return dp[x][y]을 왜 꼭 해줘야만 답이 나오는지 고민하는데도 시간이 많이 들었다.

이 사고 과정을 컨디션이 좋지 않을때도 똑같이 할 수 있을까 의문이었다,, 못 할것 같다

백준에서 다른 사람들의 풀이를 20개 정도 읽어보다가 진짜 쉽게 다이나믹 프로그래밍 하는 사람을 발견했다.

그래프가 보인다고 무조건 BFS DFS를 하는 것이 아니다. 구현 문제로 분류하고, 앞으로 나아가면서 다이나믹 프로그래밍한다.

더 쉬운 정답 코드

import sys
sys.setrecursionlimit(10**6)

N = int(sys.stdin.readline())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

direction = [(1, 0), (0, 1)]    # 하 우
dp = [[0]*N for _ in range(N)]
dp[0][0] = 1

for x in range(N):
    for y in range(N):
        if x == y == N-1:
            print(dp[x][y])
            exit(0)

        dist = graph[x][y]
        if x + dist < N:
            dp[x + dist][y] += dp[x][y]
        if y + dist < N:
            dp[x][y + dist] += dp[x][y]