이번엔 nQueens 알고리즘을 구현 해 보면서 이해하고 지나가야 했던 부분에 대해서 기록을 남겨놓으려 한다
깊이 우선 탐색과 너비 우선 탐색은..
그래프 자료구조를 탐색하는 두가지 방법이다. 목적에 따라 사용해야할 방법이 다르다.
(여기서 그래프에는 트리가 포함된다는 사실을 기억하자)
먼저 너비(Breadth) 우선 탐색은 그래프의 루트노드 부터 시작하여 인접한 노드부터 전부 순회하는 방법이다. (트리의 경우 depth 단위로 내려가며 같은 depth에 있는 노드들 먼저 전부 순회한다고 보면 된다.)
너비 우선 탐색은 재귀적으로 동작하지 않으며, 순회 할 때 어떠한 노드를 방문하였는지를 기록 또는 저장 해 두어야 한다. 그렇지 않을때 무한루프에 빠질 수 있다.
해당 그림과 같이 큐(queue)를 사용하여 순회 하였던 노드를 저장해 가며 순회하고 있다.
이때 순회 순서는 1 -> 2-> 4-> 3 이다.
깊이(Depth) 우선 탐색은 루트노드를 시작으로 먼저 최대 깊이까지 탐색한 후 그 다음 가지를 차례대로 순회하는 방식이다. (트리의 경우 한개의 자식의 자손들을 먼저 순회 후 다음 자식의 자손들을 순회하기 시작한다.)
우리가 흔히 입구가 한개인 미로를 탐험하기 위하여, 한쪽 벽을 왼손으로 짚고 계속해서 앞으로 나아가면 결국 모든 미로의 길을 탐험 후 다시 입구로 돌아오게되는 원리라고 생각하면 편할것 같다.
너비 우선 탐색보다 시간은 좀 더 걸리나, 모든 노드를 확실하게 순회하고 싶을때 사용하는 방법이다. 재귀적으로 구현하기 좋으며, 그래프의 경우 이또한 순회 할 때 어떠한 노드를 방문하였는지를 기록 또는 저장 해 두어야 한다.
!!!!깊이(Depth)가 무한(Infinity)인 구조에서는 사용할 수 없다. 무한한 순회에서 빠져나올 수 없다!!!!
그림을 보면 0에서 시작하여 하나의 길로만 계속 탐험하여 더 이상, 순회하지 않은 노드, 혹은 자식이 없을때 상위 노드로 다시 돌아오는 모습을 볼 수 있는데, 이를 Back tracking 이라 한다.
BackTracking (퇴각검색)
DFS 에서 볼 수 있는 방법이다!
말 그대로 가장 깊은곳 까지 탐색 후, 바로 전단계로 퇴각하여 깊은 곳으로 통할 수 있는
또 다른 길을 찾는다. 이또한 없을시 한단계 더 퇴각하여 같은 행동을 반복하며
결국은 root 까지 도달하여 탐색을 다시 시작한다.
