DFS(깊이우선탐색) / BFS(너비우선탐색)

그래프를 탐색하는 방법에 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 두 가지가 있다. 말 그대로 '깊이'를 우선시해서 탐색을 하는지, '너비'를 우선시해서 탐색하는 지에 차이가 있다. 아래 그림을 보며 어떻게 달라지는지 한번 비교해보자!

 

 

DFS (Depth-First Search, 깊이 우선 탐색)

---

우선 DFS는 기본적으로 최대한 깊이 내려간 뒤에, 더 이상 갈 곳이 없을 때 옆으로 이동하는 탐색 방식이다. 스택(Stack)이나 재귀(Recurse)를 이용해서 구현 가능하다. 스택으로 구현할 때는 모든 노드가 중복없이 딱 한 번씩만 담겨야 하고, 재귀로 구현할 때도 노드 방문 여부를 반드시 체크해서 무한재귀에 빠지지 않게 주의해야 한다. DFS는 모든 노드를 방문하고자 할 때 주로 사용한다.

 

탐색 과정

1. 스택에 시작노드 push, 방문체크

2. 스택 최상단 노드에

    2-1) 방문하지 않은 인접노드가 있으면 → 해당 노드 push, 방문체크

    2-2) 방문하지 않은 인접노드가 없으면 → 최상단 노드 pop

3. 2단계 반복

 

장점

1. 저장공간 많이 요구 X

    (현재 경로상의 노드만 기억하면 되기 때문)

2. 깊은 레벨에 있는 목표노드를 빨리 찾을 수 있음

3. BFS보다 간단히 구현 가능

 

단점

1. 해가 없는 경로를 탐색하면, 단계가 끝날 때까지 탐색

    (효율성을 높이기 위해 정해둔 깊이까지만 탐색하고 빠져나와 다른 경로를 탐색하는 방법을 사용하기도 함)

2. 검색 속도 자체는 BFS보다 느림

3. 해를 구한 경로가 최적의 경로라는 보장 X

    (DFS는 해에 한 번 도착하면 탐색을 종료해버리기 때문)

 

 

 

BFS (Breadth-First Search, 너비 우선 탐색)

---

BFS는 최대한 넓게 옆으로 이동한 후, 더 이상 갈 곳이 없을 때 아래로 이동하며 탐색하는 방법이다. 루트 노드(or 다른 임의의 노드)에서 시작해 다음 레벨로 넘어가기 전 인접한 노드부터 탐색한다. 시작 노드로부터 가까운 노드에 먼저 들리고, 멀리 떨어진 노드는 나중에 들리면서 노드를 '넓게' 탐색하게 되는 것이다. 큐(Queue)를 이용해 구현 가능한데, 현재 위치에서 접근 가능한 모든 노드들을 큐에 넣는 식이다. 이 때도 마찬가지로 해당 노드 방문 여부를 체크해야 한다. 주로 최단 경로를 찾고 싶을 때나, 어떤 경로를 찾고 싶을 때 사용한다.

 

+ 동적으로 무한하게 생성되는 인터넷 페이지를 크롤링할 때, 가비지 컬렉션에도 BFS 방식이 사용된다고 한다!

 

탐색 과정

1. 큐에 시작노드 enqueue, 방문체크

2. 큐에서 노드를 하나씩 꺼내며

    해당노드의 인접노드 중 방문하지 않은 노드를 모두 enqueue, 방문체크

3. 2단계 반복

 

장점

1. 가능한 경로가 여러개여도 최단 경로임을 보장

    (현재 노드에서 가까운 곳부터 찾기 때문에, 경로 탐색 시 먼저 찾는 경로가 곧 최단거리)

2. 최단경로 존재시, 깊이가 아무리 깊어져도 언젠간 찾음

3. 검색 속도 자체는 DFS보다 빠름

4. 노드 수가 적고, 깊이가 얕을 때 빠름

 

단점

1. 경로가 길어지면 메모리를 많이 요구함

    (DFS와 달리 다음에 탐색할 노드까지 저장해야 하기 때문)

2. 유한 그래프(해가 없을 때) → 모든 그래프 탐색 후 실패로 끝남

3. 무한 그래프 → 해를 찾지도, 끝내지도 못함

 

 

DFS vs BFS

---

DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
최대한 깊이! (현재 노드에서 갈 수 있는 곳까지 가봄)	최대한 넓게! (현재 노드에서 가까운 곳부터 탐색)
Stack, 재귀로 구현	Queue로 구현
ex. 경로마다 특징이 있을 때	ex. 최단경로를 찾을 때
그래프 규모가 클 때	그래프 규모가 작을 때, 시작지점-목표지점이 가까울 때