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

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

1. 깊이우선 탐색 (DFS, Depth-First Search)

한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

장점

- 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점

- 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

- 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

(2) 너비 우선 탐색(BFS, Breadth First Search)

시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법.

더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다.

장점

- 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

 

단점

- 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.