BFS와 DFS

그래프의 탐색 알고리즘인 BFS(Breadth-First Search)와 DFS(Depth-First Search)를 알아보자.

백준 저지의 단계별풀어보기에서 해당 알고리즘 문제를 풀어보자.

BFS

• 너비 우선 탐색이라 하며 BFS(Breadth-First Search)라 부른다.

• 루트 노드 혹은 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법.

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다.

• 구현에 큐를 주로 사용한다. (해당 노드의 주변부터 탐색해야 하기 때문이다.)

• 최소 비용 관련 문제에 적합한 알고리즘이다.

DFS

• 깊이 우선 탐색이며 DFS(Depth-First Search)라고 부른다.

• 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.

• 예를 들어, 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

• 스택이나 재귀함수를 통해 구현한다.

• 모든 경로를 방문해야 할 경우에(사이클 관련 문제) 적합하다.