DFS / BFS

DFS / BFS 유형

DFS, BFS는 가능한 모든 경우의 수를 체크해서 정답을 찾는 Brute-Froce(완전탐색) 문제를 해결할 수 있는 알고리즘이다.
DFS, BFS를 사용해야 하는 문제 유형으로,
1. A지점에서 B지점까지 도달하는데 걸리는 최단경로(시간)를 찾는 문제
2. 여러 정점이 주어진 상태에서 함께 연결되어 있는 정점의 개수를 구하거나, 두 정점이 같은 네트워크 안에 연결되어 있는지 확인하는 문제(네트워크)
3. 여러 조합을 전부 만들고 비교해봐야 하는 문제 ex) 부분집합 찾기
이렇게 세 개의 대표적 유형이 있다.

DFS 사용

DFS는 깊이 우선 탐색으로, 하나의 방향으로 먼저 계속 파고들며 탐색하는 알고리즘으로, 스택을 사용하거나 재귀를 사용하여 구현한다. 주로 2,3번에서 사용한다.

BFS 사용

BFS는 너비우선 탐색으로, 하나의 정점에서 도달할 수 있는 모든 정점을 큐에 넣으면서 탐색하는 방법으로, 1번 최단경로 문제는 BFS로 풀어야 한다.

DFS를 사용할까 BFS를 사용할까

어차피 둘 다 완전탐색을 하는 알고리즘이기 때문에 둘 중에 더 직관적으로 이해하기 좋은 알고리즘을 사용하면 된다. 그런 면에서 DFS가 직관적으로 이해하기 좋다. 하지만, BFS가 시간복잡도 측면에서 좋기 때문에 최단경로 문제나, 테스트 중 어려운 쪽에 나오는 문제면 BFS로 푸는 것이 좋다.