CS-STUDY/자료구조 & 알고리즘
BFS와 DFS
HwangJerry
2023. 5. 19. 14:56
BFS
- 너비 우선 탐색은 출발점에서 가장 가까운 노드부터 방문하며, 차례대로 모든 노드를 방문하는 알고리즘입니다.
- 따라서 원하는 위치가 있고, 그 위치까지 도달하는 데에 걸리는 최소 시간 또는 최단 경로를 구하고 싶다면 BFS가 적절합니다.
- BFS는 FIFO 구조인 Queue를 사용하여 로직을 구성하며, 자바에서는 LinkedList<>()로 Queue를 구현합니다.
- 그래프 문제의 공통점이지만, 이미 방문한 노드는 다시 방문하지 않을 예정이므로, 이를 감안하여 로직을 구성해야 합니다.
- 주로 길찾기 문제를 BFS로 풉니다.
DFS
- 반면에, 깊이 우선 탐색(Depth-First Search, DFS)은 시작 노드에서 가장 멀리 있는 노드를 우선적으로 탐색합니다.
- 이는 모든 경로를 탐색하고, 그 중에서 최적의 답을 도출할 때 유용합니다.
- DFS는 이론상 LIFO구조인 Stack을 사용하는데, 실제로 문제를 풀 때에는 굳이 공간을 할당하지 않고 대부분 Stack을 사용하는 대신 재귀함수 구조를 취하여 해당 효과를 누립니다. 대신 stack Overflow를 유의해야 합니다.
- DFS는 한 번 방문한 노드를 다시 방문하면 안 된다. 따라서 노드 방문 여부를 체크할 배열이 필요하고, 그래프는 인접 리스트로 표현한다.
- 만약 BFS의 queue사이즈가 엄청 커질 때에는 DFS로 푸는 게 좋습니다.
- 활용 예시는 그래프 완전 탐색이라는 기본적인 예시와 동시에, 깊은 내용으로는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬에 사용된다.