BFS와 DFS, 실생활 예시로 이해하고 언제 사용해야 할까?#

그래프 탐색을 공부하면서 BFS와 DFS라는 두 가지 탐색 방법을 배우게 되었다.

둘 다 그래프를 탐색하는 방법인데, 처음에는 이런 생각이 들었다.

“둘 다 노드를 찾는 건데 그냥 아무거나 사용하면 되는 것 아닌가?”

특히 문제를 풀면서 DFS는 한 방향으로 계속 들어가면 되기 때문에 BFS보다 코드도 간결했었다

그래서 그냥 간단한 생각으로 DFS로 하는게 좋지않을까? 라는 의문을 가졌었는데, 깊이 탐색할수록과 큐에넣어서 탐색하는과정을 고려하는걸 고민해보다가 여기까지 온것같다.

그렇다면 BFS와 DFS는 어떤 차이가 있고, 언제 무엇을 사용해야 할까?

이번에는 우리가 익숙한 지하철 노선을 예시로 BFS와 DFS의 차이를 알아보자.

지하철 노선으로 생각해보기#

민수는 현재 서울역에 있다.

서울역에서 여러 지하철 노선으로 갈 수 있고, 목적지를 찾아야 한다고 생각해보자.

이때 BFS와 DFS는 같은 지하철 노선도를 보더라도 전혀 다른 방식으로 탐색한다.

BFS: 가까운 역부터 탐색#

BFS-subway

BFS는 출발점에서 가까운 역부터 탐색한다.

서울역에서 출발하면 사진처럼 거리 순서대로 넓게 퍼져나간다.

따라서 목적지가 서울역에서 가까운 곳에 있다면, 멀리 있는 노선까지 탐색하기 전에 목적지를 발견할 수 있다.

BFS = 가까운 곳부터 넓게 탐색

특히 다음과 같은 문제가 나오면 BFS를 먼저 생각할 수 있다.

최단 거리
최소 이동 횟수
가장 가까운 노드
몇 단계 만에 도착하는지

DFS: 한 노선을 끝까지 탐색#

DFS는 BFS와 다르게 한 방향을 선택해서 최대한 깊게 들어간다.

DFS-subway

위 그림처럼서울역에서 출발해서

A → B → C → D → E → F
→ G → H → I → J → K

다시 돌아온다.

그런데 K까지 갔는데 목적지가 없다면?

다시 돌아오면서(Backtracking) 아직 탐색하지 않은 다른 경로를 확인한다.

위 예시에서는 결국 서울역에서 가까운 시청역(M)을 발견한다.

목적지가 가까이에 있었더라도 다른 경로를 먼저 깊게 탐색하면 한참 돌아서 발견할 수 있다.

DFS = 한 방향을 깊게 탐색

그렇다면 BFS가 더 좋은 것 아닌가?#

꼭 그렇지는 않다.

BFS와 DFS는 누가 더 좋은 알고리즘인지의 문제가 아니라 탐색 순서의 차이이다.

BFS#

“가까운 역부터 확인하자.”

출발점 > 가까운 노드 > 그다음 가까운 노드 > 더 먼 노드

최단거리나 최소 이동 횟수처럼 가까운 곳부터 탐색해야 하는 문제에 유리하다.

DFS#

“일단 이쪽부터 끝까지 가보자.”

모든 경우를 탐색하거나 한 방향으로 깊게 들어가야 하는 문제에 유리하다.

BFS와 DFS의 메모리 차이#

BFS와 DFS를 비교할 때 메모리 사용량도 생각해볼 수 있다.

BFS는 현재 거리에서 탐색해야 할 노드들을 큐에 저장하면서 탐색한다.

그래프가 넓게 퍼져 있다면,

              A
        ┌─────┼─────┐
        B     C     D
      ┌─┼─┐   │   ┌─┼─┐
      E F G   H   I J K

같은 레벨에 있는 많은 노드를 큐에 저장해야 할 수 있다.

BFS는 그래프가 넓게 퍼질수록 큐에 저장해야 하는 노드가 많아질 수 있다.

반대로 DFS는 한 방향으로 깊게 들어가면서 현재 탐색 경로를 스택에 저장한다.

A
↓
B
↓
C
↓
D
↓
E
↓
...

따라서 그래프가 매우 깊다면 DFS의 스택 또는 재귀 호출이 깊어질 수 있다.

DFS는 그래프가 깊어질수록 스택 메모리를 많이 사용할 수 있다.

“BFS가 메모리를 많이 사용하고 DFS는 적게 사용한다.”

라고 외우는 것은 정확하지 않다.

BFS는 너비가 넓을수록, DFS는 깊이가 깊을수록 메모리 사용량이 증가할 수 있다.

시간복잡도는?#

인접 리스트로 그래프를 표현했을 때 일반적인 BFS와 DFS의 시간복잡도는 둘 다

O(V + E)

이다.

V = 정점(Vertex)의 개수
E = 간선(Edge)의 개수

따라서 DFS가 코드가 더 간단하다고 해서 무조건 BFS보다 빠른 것은 아니다.

둘의 핵심적인 차이는 시간복잡도보다는 탐색 순서와 메모리 사용 방식에 있다.

핵심 요약: 언제 뭘 써야 할까?#

상황	추천 알고리즘	이유
최단 거리 / 최소 횟수를 구해야 할 때	BFS	가까운 노드부터 탐색하므로 처음 목적지에 도달한 경로가 최단거리
모든 노드를 방문해야 할 때	둘 다 가능	단순 전체 탐색이라면 둘 중 편한 것을 선택
그래프가 넓게 퍼져 있을 때	DFS 고려	BFS는 같은 레벨의 많은 노드를 큐에 저장할 수 있음
그래프의 깊이가 매우 깊어질 수 있을 때	BFS 고려	DFS는 스택이나 재귀가 깊어질 수 있음
모든 가능한 경로를 탐색해야 할 때	DFS	한 경로를 끝까지 탐색한 뒤 돌아오는 방식이 자연스러움
각 갈림길마다 상태를 유지해야 할 때	DFS	재귀를 이용하면 현재 경로의 상태를 관리하기 쉬움

마무리#

결국 BFS와 DFS 중 무조건 더 좋은 알고리즘은 없다.

중요한 것은 문제를 보고 어떤 탐색 순서가 필요한지 판단하는 것이다.

최단거리나 최소 이동 횟수가 필요한가?

→ BFS

한 방향으로 깊게 탐색하거나 모든 경우를 확인해야 하는가?

→ DFS

결국 BFS와 DFS의 차이를 가장 간단하게 표현하면,

BFS = 가까운 곳부터 탐색

DFS = 한 방향으로 깊게 탐색

이라고 정리할 수 있다.

BFS와 DFS는 지하철 노선뿐만 아니라 미로 탐색, SNS 친구 관계, 파일 시스템, 게임 경로 탐색, 네트워크 연결 확인 등 다양한 곳에서 활용된다.

나는 코드의 모양만 외우기보다는 “나는 가까운 곳부터 찾아야 하는가, 아니면 깊게 들어가야 하는가?”를 먼저 생각하고 알고리즘을 판단하는게 중요하다고 느꼈다.