Algorithm] 경로 탐색 - 2

이전 포스팅에서도 말했다시피, 일반적인 재귀 방법을 사용하는 건 시간이 오래 걸린다는 단점을 가지고 있다.

메모화재귀는 동적계획법을 재귀적으로 사용하는 것으로 동적계획법의 일종으로

한 번 계산이 진행된 것은 추가로 진행하지 않는 것을 목표로 하기 때문에

깊이 우선 탐색을 응용해 (1,1)에 하위에서 생성된 계산값을 미리 작성해두어

만일 다시 접근이 이뤄지면 그 값을 반환시키는 것을 말한다.

깊이 우선 탐색을 통해서 일반적인 재귀 방법으로 접근했을 때 중복되는 작업들을 많이 걸러낼 수 있어서

제한 시간 초과라는 문제를 극복할 수 있다.

const int h = 5, w = 4;
int Memo_recursion[h + 1][w + 1];

int dfs(int nowh, int noww)
{
	if (nowh > h || noww > w)
		return 0;
	if (nowh == h && noww = w)
		return 1;
	if (Memo_recursion[nowh][noww] != 0)
		return Memo_recursion[nowh][noww];
	return Memo_recursion[nowh][noww] = dfs(nowh + 1, noww) + dfs(nowh, noww + 1);
}

메모화재귀, 깊이 우선 탐색 다 뒤로 하고, 동적계획법으로 이 문제를 접근해보자.

깊이우선탐색과 메모화재귀를 사용하게 된 근본적인 이유는

트리형식의 구조에서 여기서부터 가는 방법을 도출해내려고 했기 때문인데

동적계획법은 그럴 필요도 없고 재귀를 사용하지 않아

재귀를 어려워하는 사람들에게는 오히려 쉽게 느껴질 수도 있다.

사실 대부분의 사람들이 어릴 적에 이런 경로 탐색 문제를 풀면서 동적계획법을 사용했다.

놀랍게도, 각 교점에 오는 최단 경로수를 적어두는 것이 부분 최적해를 구하는 과정이니까..

const int h = 5, w = 4;
int dp[h + 1][w + 1];
void Dynamic()
{
	int i, j;
	dp[0][0] = 1;
	for (i = 0; i <= h; i++)
	{
		for (j = 0; j <= w; j++)
		{
			if (i != 0)
				dp[i][j] += dp[i - 1][j];
			if (j != 0)
				dp[i][j] += dp[i][j - 1];
		}
	}
}

(i,j){단, i>0 이거나 j>0)라는 교점에 도달하려면, 반드시 (i-1,j) 혹은 (i,j-1)을 경유하므로

직전 포인트인 이 두 정점에 도달하는 방법을 더하면 (i,j)에 도달하는 방법이 된다.

위 코드는 이런 식의 과정을 반복문으로 표현한 코드다.

배열 크기를 실제 주어진 높이(h)와 넓이(w)보다 하나씩 더 큰 값을 주는 이유는 두 방법은 각 지점을 기준으로 판단하기 때문이다.

B

A

선들이 만나 생기는 교점은 h+1, w+1이라는 점이다.

따라서, 코드 내에서도 dp[0][0]인 시작점을 1로 잡아 시작하고

최종적으로 우리가 원하는 값은 dp[5][4]에서 얻을 수 있다.