DFS + 메모이제이션(DP)

dfs는 데이터의 개수가 조금만 커져도 시간초과가 날 확률이 높은 방법이다.

왜냐하면 50x50칸의 2차원 배열이 있을때 0,0에서 50,50으로 가는 경우의 수를 찾을때 dfs를 사용해야 하고, 상하좌우 네방향으로 이동 가능하다고 했을때

4의(50x50)승이라는 어마어마한 연산의 횟수가 발생한다. 물론 범위 벗어나는거 제외하고 이러다보면 저것보단 적겠지만, 어쨌든 그래도 엄청난 연산횟수라는것은 부정할수없다.

그렇기 때문에 우리는 같은 계산을 피해야 한다.

그것이 바로 동적계획법(Dynamic Programming)이고 다른말로 메모이제이션이라고도 한다. 

즉 DFS는 DFS인데 예전에 구해놨던 값이 있으면 그 값을 쓰겠다는 뜻이다. 

예를 들어 0,0에서 1,1을 거쳐 50,50으로 가는 경로가 있다고 하자 (50x50 2차원 배열을 떠올리자)

그런경우 

1. 0,0에서 오른쪽->아래 순서로 1,1으로 간 후 50,50으로 가는 경로가 생길수있고,

2. 0,0에서 아래->오른쪽 순서로 1,1에 간 후 50,50으로 가는 경로가 생길수있다.  

첫번째 경우에서 DP[1][1] = (1,1에서 50,50으로 가는 경로수)를 기록해 놓으면 

2번째 경우에서 1,1에 왔을때 이미 DP에 계산된 결과를 메모해놓았으므로 또다시 계산할 필요 없이 그 값을 그대로 쓰면 된다. 

어차피 1,1에 온 이상  1,1 까지 어떻게 왔던지 간에 50,50까지 가는 경로는 똑같을 것이기 때문이다.

이렇게 해주게 되면 중복된 계산을 피할 수 있게 되며 딱 필요한 만큼의 계산만 하게 되므로 연산 횟수가 매우매우 크게 줄어들게 된다.

그래서 DFS를 데이터가 큰 경우에도 사용할수 있게 된다.

백준에 이것을 적용시키기 아주 좋은 문제가 있어서 소개한다. 궁금하신분은 꼭 풀어 보는것을 추천한다. 내가 위에서 말한 내용을 그대로 적용시킨 문제이다.

백준 1520번 내리막길

위에서 내가 얘기한 방법은 TOP-DOWN방식이다.

보통 TOP-DOWN방식은 재귀함수로 구현을 한다.

위 예제를 통해서 예를 들어보면 DFS를 통해 쭉쭉 들어가다가 (50,50)에 도달한 경우 RETURN 1을 해준다. 그렇게 되면

(49,50) (50,49)에 1이 들어갈것이고,

쭉 경로를 타고 1이 들어가게 될것이다. 이처럼 맨 위에서 아래로 내려오면서 값이 채워지는것을 top-down방식이라고 한다.

그 다음은 DOWN-UP방식이 있는데 이것은 for문으로 구현을 한다.

(2,2)까지 오는 경로는 (1,2)까지 오는 경로 + (2,1)까지 오는경로를  더한것을 넣어주면 된다. 이런식으로 (50,50)까지 반복문을 돌리면 DP[50][50]에는 (0,0)에서 (50,50)까지 가는 경로의 수가 저장되게 된다.

즉 똑같은 DP문제를 두가지 방식으로 풀 수 있고, 위의 1520번 문제는 그중에서도 탑다운방식으로 해야 쉽게 풀리는 문제이다.

즉 탑다운 방식은 (x,y)가 있을때 (x,y)에서 (0,0)까지 가는 경로의수 라고 해석을 하면 되고

다운업 방식은 (x,y)가 있을떄 (0,0)에서 (x,y)까지 오는 경로의수 라고 해석을 하면 된다.