BFS와 DFS

BFS

• 너비 우선 탐색은 출발점에서 가장 가까운 노드부터 방문하며, 차례대로 모든 노드를 방문하는 알고리즘입니다.
• 따라서 원하는 위치가 있고, 그 위치까지 도달하는 데에 걸리는 최소 시간 또는 최단 경로를 구하고 싶다면 BFS가 적절합니다.
• BFS는 FIFO 구조인 Queue를 사용하여 로직을 구성하며, 자바에서는 LinkedList<>()로 Queue를 구현합니다.
• 그래프 문제의 공통점이지만, 이미 방문한 노드는 다시 방문하지 않을 예정이므로, 이를 감안하여 로직을 구성해야 합니다.
• 주로 길찾기 문제를 BFS로 풉니다.

2178번: 미로 탐색

[BFS/자바] 백준 2178. 미로 탐색

DFS

• 반면에, 깊이 우선 탐색(Depth-First Search, DFS)은 시작 노드에서 가장 멀리 있는 노드를 우선적으로 탐색합니다.
• 이는 모든 경로를 탐색하고, 그 중에서 최적의 답을 도출할 때 유용합니다.
• DFS는 이론상 LIFO구조인 Stack을 사용하는데, 실제로 문제를 풀 때에는 굳이 공간을 할당하지 않고 대부분 Stack을 사용하는 대신 재귀함수 구조를 취하여 해당 효과를 누립니다. 대신 stack Overflow를 유의해야 합니다.
• DFS는 한 번 방문한 노드를 다시 방문하면 안 된다. 따라서 노드 방문 여부를 체크할 배열이 필요하고, 그래프는 인접 리스트로 표현한다.
• 만약 BFS의 queue사이즈가 엄청 커질 때에는 DFS로 푸는 게 좋습니다.
• 활용 예시는 그래프 완전 탐색이라는 기본적인 예시와 동시에, 깊은 내용으로는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬에 사용된다.

11724번: 연결 요소의 개수

 

[DFS/자바] 백준 11724. 연결 요소의 개수