백준 1520번 - 내리막 길

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

1520번: 내리막 길

 

길찾기 문제 + 경로 개수 찾기 문제이다.

 

만약 이 문제가 내리막길을 찾으면서 가장 빨리 도착해야겠다면 다익스트라 혹은 BFS문제였을 것이다. 그러나 이 문제는 경로의 개수 를 찾는 문제이다. 

 

답만 찾으려면 dfs로 조건만 돌리면 되지만, 이렇게하면 4^500*500 으로 당연히 시간초과가 난다. 그러므로 메모이제이션을 통해 지금이 노드를 이용하면 마지막 노드까지 갈 수 있는지 없는지를 저장해놔야한다. 

즉, dp[i][j] = i,j 에서 N -1, M - 1까지 갈 수 있는 경로의 수를 저장함으로서 중복된 탐색을 더 하지 않도록 한다.

 

그림으로 설명하면

 

이렇게 경로를 갈 수 있다고 하자. 그럼 지나온 모든 경로 지점들의 dp[i][j] = 1이 될 것이다.

 

 

그 후 빨간색 경로로 이동하다가 2,2를 만났다고 하자. 그렇다면 이후 빨간색 경로는 파란색경로를 그대로 따라가게 될 것이다. 이것은 시간 낭비이다. 그러나 dp[2][2]에는 1이라는 경로가 들어있다. 그러므로 dp[1][2] += dp[2][2] 를 사용하여 더 탐색하지 않고도 이 길로 가면 더 길이 있음을 알 수 있다. 

 

그리고 이렇게 각자 탐색을 끝낸 가지들은 최우단으로 갈 수 있는 경로의 개수를 모두 담아 dp로 돌려줄 것이다. 그러므로  dp[0][0]이 정답이 될 수 있다. 

 

이 문제의 핵심은 두가지이다.

1. 왜 bfs가 아닌 dfs인가?

 - 각 노드마다 따져야할 것이 있고, 단순 최단거리가 아니다. 그리고 재귀적 요소가 필요하다.

2. 왜 dp를 사용해야하는가?

- 그래프 탐색만으로 풀이하면 시간초과가 발생한다. 중복된 탐색을 피하기 위해 메모이제이션이 필요하다.

 

1년전에 내가 이걸 풀었다고? 구글링이었을 것이다 ㅉ..