[Algorithm] DFS & BFS

[Algorithm] 깊이 우선 탐색과 넓이 우선 탐색 (DFS and BFS)

그래프 알고리즘으로, 각 상황에 맞춰 잘 사용하자. 경로 찾는 문제에서 자주 쓰인다.

DFS(Depth-First Search)

• 깊이 우선 탐색.
• 루트 노드 혹은 임의의 노드에서 다음 브랜치로 넘어가기 전 해당 브랜치를 모두 탐색하는 방법.
• 스택 or 재귀 함수로 구현.
• 모든 경로를 방문해야 할 경우 적합.

시간 복잡도

V는 접점, E는 간선

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)

BFS(Breadth-First Search)

• 넓이 우선 탐색.
• 루트 노드 혹은 임의의 노드에서 인접한 노드부터 먼저 탐색하는 방법.
• 큐(queue)를 통해 구현한다. (해당 노드 주변부터 탐색해야 하므로)
• 최소 비용 우선일 때 적합

시간 복잡도

V는 접점, E는 간선

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)