[알고리즘] DFS, BFS (깊이/너비 우선탐색)

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

:루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

 

1. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함

2. 즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색함 

3. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

4. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하지만, 속도는 BFS에 비해 느림

출처 출처 https://developer-mac.tistory.com/64

• 스택 자료구조를 이용하여 표현(FILO 방식)
• 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 그 후 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리를 하는 과정을 반복(더 이상 못 할 때까지)
• 경로의 특징을 저장해야 하는 경우(길 찾기 같은)에 사용된다

2 BFS(Breadth-First Search) ; 너비 우선 탐

1. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
2. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순서(순회)
3. 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용하게 된다

• 큐(Queue) 자료구조를 이용하여 표현(FIFO 방식)
• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다(스택이 큐로 바뀐 거 빼고는 모든 게 동일)
• 찾는 노드가 인접하다면 유리하지 노드가 많을 수록 메모리를 많이 소비
• 웹크롤러 동작 시 사용되는 방식이다

 

---