Algorithm] 길찾기( 재귀와 동적계획법)

길찾기 문제다.

정/직사각형 도시에서 출발지부터 목적지까지 가는 길의 경우의 수를 구한다.

풀이방법은 재귀적인 방법과 동적계획법(Dynamic Programming)을 이용한 방법이 있다.

왼쪽 위의 그림은 찾아가야하는 MAP이다. 오른쪽 위의 그림은 왼쪽의 MAP을 ARRAY화 해서 변경한 그림이다. 가지 못하는 길은 0, 아니면 1을 기록한다. 이렇게 정해진 2*2 Array를 이용해서 풀이를 시작한다.

1. 재귀적인 풀이

재귀적인 풀이는 목적지(m,n)로부터 (0,0)까지 재귀를 통해 답을 얻어낸다. 함수가 실행되면 시작점까지 계속 함수를 콜해서 값을 리턴해나가며 최종적으로 경우의 수를 구해낸다. 구현한 코드에서는 메모이제이션을 수행하지 않았기때문에 m,n이 커질수록 연산이 엄청나게 늘어난다.

2.동적계획법

동적계획법을 이용하면 (0,0)부터 for문을 돌면서 풀이를 해나간다. 그냥 일반적으로 생각하는 것처럼 for문을 돌면서 이전 값들을 새로운 Array에 기록해나가면서 최종적으로 값을 얻는다. 재귀에 비해서 연산이 매우 빠르다.

만약 못가는 길이 없는 MAP에서 가중치가 주어진 MAP이라면 아래와 같은 함수를 CALL하면 된다.

출력은 다음과 같다.