[알고리즘] DFS, BFS, 백트래킹

DFS vs BFS

- 모든 경우의 수를 고려하는 문제 -> DFS

-> BFS로 구현시 큐의 크기가 커진다.

 

- 트리의 깊이가 큰 경우 -> BFS

-> DFS로 구현시 무한 루프 발생

 

- 최단 거리 구하기 -> BFS

 

깊이 우선 탐색 DFS

- 트리에서 말단까지 도착할 때까지 한 쪽 방향으로만 내려가는 방식

- 말단에 도착하게 되면 다시 돌아와서 다른 방향으로 간다.

 

백트래킹

- DFS 활용

- 해를 찾는 도중, 찾는 해가 아닐 경우 되돌아가서 해를 찾는 방법

- ex) N-Queen

 

너비 우선 탐색 BFS

- 모든 분기점을 다 검사하면서 진행

- Queue 사용

 

최선 우선 탐색

- BFS에서 업그레이드 된 방식

- 우선순위 큐 사용

- 현재 가장 최적인 경우를 우선적으로 검사하기 때문에 BFS보다 상대적으로 효율적이다.