1520

[python3] 백준 1520 풀이 ( 내리막길, DP, DFS, 그래프 )

이번 문제 풀이 사실 봐버렸다. 거의 풀었다고 생각했는데 내가 생각한 방법으로는 도저히 풀리지가 않아서 그냥 풀이를 봤다. 바로 문제를 보자 문제를 읽어보면 낮은 방향으로만 진행한다고 한다. -> 사이클이 존재하지 않는 그래프이다. 가장 빠른게 도착하는게 아닌 도착하는 경우의 수를 구한다. -> BFS가 아닌 DFS를 여러 번 써야한다. 문제를 통해 2가지를 확인할 수 있다. 그런데 DFS만을 쓰는 경우에는 너무 많은 케이스가 존재한다. 실제로 DFS만으로 제출한다면 시간초과가 뜬다. 따라서 DFS만이 아닌 DP를 함께 활용해 주어야한다. 그럼 DP를 어떻게 활용해야 할지 고민을 해본다. DFS만 써서 시간초과가 나는 것은 빙빙 돌아 목적지에 도착하는 경우까지 기다려야 하기 때문이다. 그렇다면 빙빙 돌아..