DFS와 BFS에 대해 알아보자.

목차
1. DFS란 무엇일까?
2. BFS란 무엇일까?
3. DFS와 BFS의 차이점

 

1. DFS란 무엇일까?

DFS(Depth-Frist Search)는 깊이 우선 탐색이라고도 말한다. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 즉, 넓게 탐색하기 전에 깊이 탐색하는 것이다.

DFS는 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 참색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

 

 

DFS의 장점

• 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
• 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일때 유용하다
• DFS를 사용하여 그래프에서 순환을 감지할 수 있다.

DFS의 단점

• 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
• 두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 가장 좋은 알고리즘이 아닐 수 있다.

DFS는 특정 시나리오에서 매우 유용할 수 있지만 항상 최선의 선택은 아니다. 해결하려는 특정 문제에 따라 BFS와 같은 다른 알고리즘이 더 적합할 수 있다.

 

 

2. BFS()란 무엇일까?

BFS(Breadth-First Search)는 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다. 두 노드 사이의 최단 경로 혹인 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

BFS는 마치 물고기가 연못을 헤엄치며 주위를 둘러보는 것과 비슷하다. 물고기가 연못의 가장자리부터 시작해서 점점 넓게 퍼져가면서 모든 곳을 살펴보는 것처럼, BFS도 시작점에서부터 가까운 곳부터 차례대로 탐색을 해나간다.

 

예를 들어, 내가 어떤 친구와 놀고 싶은데, 나와 가까운 친구부터 먼저 찾는다고 생각해보자. 나의 친구들은 나와 가까운 순서대로, 즉 집에서 가까운 순서대로 차례대로 찾아가면서 "나와 친구인가?"를 물어보는 것이다. 만약 그 친구가 나와 직접적인 연결이 되어있다면 그 친구를 선택하고, 연결된 모든 친구들을 확인할 것이다. 이렇게 하나의 친구부터 시작해서 넓게 퍼져가면서 친구들을 탐색하는 것이다.

그래서 BFS는 먼저 가까운 곳을 찾아보면서 점점 더 멀리 있는 곳을 탐색해 나가는 것이다. 이 방법을 사용하면 두 지점사이의 가장 짦은 길이나 경로를 찾을 수 있을 것이다. 만약 내가 집에서 학교까지 가장 빠른 길을 찾고 싶을 때 BFS를 이용한다.

 

 

BFS의 장점

• 간단하고 이해하기 쉬운 편이다.
• 연결된 구성 요소에서 모든 노를 찾는 데 사용할 수 있다.

BFS의 단점

• 많은 메모리가 필요하므로 큰 그래프에는 적합하지 않다
• 그래프를 순회할 때 가중치를 고려하지 않기 때문에 가중치 간선이 있는 그래프에는 적합하지 않다.
• 다음 깊이로 이동하기 전에 노드의 모든 하위 항목을 탐색하기 때문에 분기 계수가 큰 그래프에는 비효율적이다.
• 다음 깊이로 이동하기 전에 현재 깊이의 모든 노드를 방문하기 때문에 노드 수가 많은 그래프에는 비효율적이다.
• 목표 노드가 시작 노드에서 멀리 떨어져 있으면 다음 깊이로 이동하기 전에 주어진 깊이의 모든 노드를 탐색하기 때문에 비효율적이다.

BFS는 메모리를 많이 사용하고, 노드 수가 많은 그래프에는 적합하지 않으며, 가중 간선이 있는 그래프에서는 제대로 작동하지 않는다는 점을 알아두는 것이 중요하다.

 

 

DFS와 BFS의 차이점

1. 탐색 방식
   • DFS는 깊이 우선 탐색으로, 한 분기를 끝까지 탐색한 후 다음 분기로 넘어간다.
   • BFS는 너비 우선 탐색으로, 한 레벨의 모든 모든 노드를 방문한 후에 다음 레벨로 넘어간다.
2. 탐색 순서
   • DFS는 한 분기를 완전히 탐색한 후에 다른 분기로 넘어가므로, 같은 깊이에 있는 노드를 먼저 탐색한다.
   • BFS는 한 레벨의 모든 노드를 먼저 탐색하므로, 같은 깊이에 있는 모든 노드를 동시에 탐색한다.
3. 메모리 사용
   • DFS는 깊은 곳까지 탐색하기 때문에 현재 경로 상의 노드들만 기억하며 되므로 스택을 이용하여 메모리를 적게 사용한다.
   • BFS는 너비 우선 탐색으로 모든 인접 노드를 큐에 추가하기 때문에 메모리 사용량이 많을 수 있다.
4. 시간 복잡도
   • DFS는 깊이에 따라 빠를 수도, 느릴 수도 있지만, 그래프가 깊은 경우 최악의 경우 시간 복잡도가 높을 수 있다.
   • BFS는 너비 우선 탐색으로 최단 경로를 찾을 수 있지만, 노드 수가 많은 경우에는 모든 노드를 방문해야 하므로 시간 복잡도가 높을 수 있다
5. 적합한 문
   • DFS는 루프에서 깊이가 중요한 문제나 순환을 찾는 문제 등에 적합하다.
   • BFS는 최단 경로를 찾는 문제나 깊이가 크게 중요하지 않은 문제에 적합하다.