Chap 4. DFS, BFS, 백트래킹 - DFS 와 BFS 차이점

DFS, BFS 

 

1. 공통점 

 

둘 다 완전 탐색 알고리즘이므로

모든 경우의 수를 다 살펴봄. 반드시 답을 찾을 수 있음.

대신, 느리다는 단점을 가지고 있음.

 

 

2. 차이점

 

탐색 순서가 다름.

DFS는 Depth를 기반으로 탐색한다.

'5' 노드를 최단거리로 찾는다고 가정하면,

Depth 가 아닌 Breadth 가 맞음.

0에서 시작해 Depth 기반으로 5를 만났을 때는 , 이게 최단거리로 온거라는 걸 보장할 수 없음. 딴 거 다 둘러보고 왔을 수도 있음.

그래서, 정말로 모든 경로를 다 가보면서 어떨 때 5를 만났는지, 또 그 거리는 몇인지를 기록해야함.

 

반면, Breadth 기반으로 탐색한다가 5를 만났다면, 그게 곧 최단거리 경로이고 더 이상 탐색할 필요가 없음.

그럴 수 밖에 없는 이유가 

 

0 에서 거리가 1인 노드들 : 1, 2

0에서 거리가 2인 노드들 : (1로 부터 들어온) 3,4, (2로부터 들어온) 5,6

이런 식으로 큐에 들어가기 때문에, bfs 로 탐색하다가 5를 만났다면 그 경로는 최단 거리 경로일 수 밖에 없는 거임.