[Algorithm] 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS)

BFS (Breadth-First Search)

 

• 시작 노드에서 가장 가까운 노드부터 시작하여 모든 노드 광범위하게 탐색
• 첫번째 floor부터 시작해서 해당 floor의 모든 노드 방문할 때까지 수평 이동
• 한 번 거친 노드 순서 저장한 후 다시 꺼내는 FIFO 
• 주로 Queue로 구현

 
 

DFS (Depth-First Search)

 

• 시작 노드와 직접 연관된 하위 노드의 끝까지 모두 탐색한 후 다음 하위 노드 탐색
• 경로 하나의 모든 floor 탐색한 뒤 그 다음 경로의 모든 floor 탐색하는 순서
• 주로 재귀호출이나 Stack 명시하는 방법으로 구현