C_7. DFS & BFS

7. DFS & BFS

1. DFS (Depth First Search) - 깊이 우선 탐색 알고리즘

기준이 되는 노드로부터 멀리 있는 노드, 즉 깊이가 있는 노드를 우선시해서 탐색하는 것

DFS의 구현을 위해서는 

• 스택: 경로 정보의 추적을 목적으로 한다. 

• 배역: 방문 정보의 기록을 목적으로 한다. 

2. BFS (Breadth First Search) - 너비 우선 탐색 알고리즘

기준이 되는 노드로부터 가까이 있는 노드, 즉 깊이가 얕고 너비를 넓고 탐색하는 것

BFS의 구현을 위해서는 

• 큐: 방문 차례의 기록을 목적으로 한다. 
• 배열: 방문 정보의 기록을 목적으로 한다. 

※ DFS와 BFS는 실전에서 쓰기에는 많이 느린 알고리즘에 속한다. 

 

 

3. 되추적법, 백트레킹(Backtraking)

문제 해결을 위해 상태공간트리(state space tree), 깊이 우선 탐색(DFS)가 사용됐다. 

유망하지 않은(non-promising) 노드는 가지쳐서(pruning) 검색을 하지 않고, 유망한(promising) 노드에 대해서만 그 노드의 자식노드를 검색한다. 

즉, 어떤 결정들을 내려가다가 더 이상 진행할 수 없을 때, 가장 최근에 내린 결정을 번복하고 다시 뒤로 돌아가 다른 선택을 하면서 문제를 해결하는 것. 

ex) 스도쿠, N-Queen

 

 

4. 분기한정법(Branch and bound)

문제 해결을 위해 상태공간트리(state space tree)가 사용됐다. 

백트레킹과는 다르게 DFS, BFS 등 상태 공간 방문법에 특별히 구애받지 않아서 트리를 탐색하는 방법에 제한이 없고, 최적화 문제에서만 사용된다.