반응형

재귀 2

미로찾기 알고리즘(recursive)-재귀

미로찾기 알고리즘의 종류는 여러가지가 있다. 이 글은 그 중에서 가장 기본이 되는 재귀(recursive) 알고리즘에 관한 글이다. 재귀의 특징은 직관적으로 알아보기 쉽다는 이점이 있다. 재귀는 Stack을 사용하기 때문에 깊이가 깊어지면 overflow 에러가 날 가능성이 높아진다. 하지만, 간단한 문제에 대해서는 재귀의 유혹을 뿌리치기 힘들다. 이전에 알아봤던 깊이 우선 탐색은 미로찾기 알고리즘(재귀)의 원형이 된다. 2014/02/26 - [프로그래밍/알고리즘] - 하노이탑 재귀호출 알고리즘 2013/06/05 - [프로그래밍/알고리즘] - 탐색-깊이우선탐색, 너비우선탐색 오래전 포스팅한 내용이라... 예를 들어보면. 위와같은 길이 있다고 하자. 1.어두운 블럭은 벽으로 막혀 있다고 가정하고, 하얀..

탐색-깊이우선탐색, 너비우선탐색

아래 1부터 7 까지의 노드들이 있다. 이런 노드들을 연결해놓은 아래와 같은 그림을 그래프라고한다. 트리와 그래프의 차이는 트리는 한 노드에서 또다른 노드까지 가는 방법이 1가지인데 반해 그래프는 여러가지방법이 있을 수 있다. 이제 깊이 우선 탐색을 알아보겠는데 깊이란 시작점에서 부채모양으로 퍼진형태가아닌 선형태로 탐색을 하는 것을말한다. 그림에서 1-2-4-7 , 1-2-5-6 이런식으로 탐색해 나가는것이 깊이 우선 탐색이라고 한다. 너비우선탐색은 (1-2 ,1-3) (2-4,2-5) 이런식으로 시작점을 정하면 부채꼴모양으로 가능한 연결수를 다 찾아낸후 다음 탐색을 하는 형태이다. 깊이우선탐색은 시작정점의 변경이 한번의 이동에 한번씩 된다. 하지만 너비우선탐색은 시작정점이 있으면 연결된 노드를 다 탐색..

반응형