DFS와 BFS의 성능 차이

[Eunno-An]

경주로 문제의 DFS해법과 BFS해법 중
DFS는 시간 초과가 나고, BFS는 통과??

[Eunno-An]

인공지능에서도 비슷한 문제를 경험한 적이 있음. 좀 더 폭 넓게 탐색하는 것이 탐색에는 더 유리하다고 했던 것 같음.

[Eunno-An]

3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

​

1. 그래프의 모든 정점을 방문하는 것이 주요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.

둘 중 편한 것을 사용하시면 됩니다.

​

2. 경로의 특징을 저장해둬야 하는 문제

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

3. 최단거리 구해야 하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

출처: https://devuna.tistory.com/32 [튜나 개발일기]

[Eunno-An]

DFS는 재귀를 돌기 떄문에 매개변수 복사시에 오버헤드가 많이 발생함.

[Eunno-An]

위 이슈가 발생할 수 있는 문제들로는

1. 프로그래머스 Level3 보행자천국
   https://programmers.co.kr/learn/courses/30/lessons/1832#qna
2. 프로그래머스 Level3 가장먼노드
   https://github.com/Eunno-An/Programmers/blob/main/Lv3/★가장%20먼%20노드.cpp
3. 프로그래머스 Level3 경주로건설(1번문제와 상당히 유사함)
   https://github.com/Eunno-An/Programmers/blob/main/Lv3/★★★경주로%20건설.cpp