Algorithm] 경로 탐색 - 1

B

A

아마 고교시절 순열조합 부분에서 자주 접하는 문제 중 하나로,

A 지점에서 B 지점으로 갈 때 최단거리의 경우의 수가 얼마나 되는지 구하는 것이 목표인 문제다.

깊이우선탐색을 사용할 때, 모든 기점마다 경로를 선택해야 하고 이 경우 30번정도 그런 과정이 필요하다.

따라서 Big O는 O(2^(w+h))가 되어 2^30인데 10억이 넘어가는 수치가 된다.

연산 시간이 오래 걸려 썩 좋은 방법이 아니다.

우리는 이 문제를 고교시절 기계적으로 푸는 방법을 터득한 바 있다.

바로 이항정리에 근거한 조합을 이용하는 방법이고

9C4=126이라는 정답에 빠르게 근접할 수 있다.

Big O 또한 O(w+h)로 계산량도 적어 매우 효율적으로 보인다.

그러나, 이는 모든 지점을 통과할 수 있을 때나 가능하다는 제한적인 케이스에서 매우 효율적인 것이다.

물론 뛰어난 수학적 사고력을 가지고 있는 사람이 복수의 지점에서의 통행이 불가능해도

수학적으로 풀어낼 수 있다고 주장할 수도 있겠지만, 우리는 컴퓨터라는 도구를 이용하기 때문에

반복되는 과정을 컴퓨터를 대신해 풀 필요가 없다.

일단 일반적인 재귀를 사용해 깊이 우선 탐색을 선택하면 경로탐색 문제를 아래와 같이 해결할 수 있다.

일단 시작을 0,0으로 보고 최종 목적지가 5,4라고 할 때 현재 좌표를 (nowh, noww)라고 하자.

이 때, (nowh+1, noww)와 (nowh, noww+1)에 대해서 모두 검사를 진행하는 것을

탐색트리로 작성하면 포화이진트리가 그려진다.

이를 바탕으로 최단 경로를 구하는 코드는 아래와 같다.

const int h = 5, w = 4;
int dfs(int nowh, int noww)
{
	if (nowh > h || noww > w)
		return 0;
	if (nowh == h && noww = w)
		return 1;
	return dfs(nowh + 1, noww) + dfs(nowh, noww + 1);
}

위의 경로탐색 과정대로 진행하기 앞서 이진트리를 작성해보면 필요 없는 동작이 눈에 보이는데,

(0,1)->(1,1), (0,2) / (1,0)->(2,0), (1,1)로 두 번의 (1,1)에서의 동작이 있다.

이후에는 (1,2), (2,1)에서 필요 이상의 동작이, (1,3), (2,2), (3,1)에서도 비슷한 문제가 발생하고

지속적으로 이러한 불필요한 동작이 발생하여 선택 가능한 경로가 늘어날수록

이러한 불필요한 반복 횟수가 폭증한다는 단점이 있다.

이 문제를 해결할 수 있는 방법에 대해서는 다음 포스팅에서 이어서 다뤄보자.