[ 완전 탐색 ] DFS / BFS

 

완전탐색[전탐색]

완전탐색은 고려할 수 있는 모든 경우의 수를 탐색하여 적합한지 부적합한지 확인하는 것이다. 이는 모든 경우에 솔류션이 될 수 있지만, 적합한 솔류션은 아닙니다. 왜냐하면 데이터 양이 증가하면 할수록 경우의 수가 많아 한정된 시간에 모든 경우의 수를 탐색할 수 없기 때문입니다. 하지만, 데이터 양이 한정되어 있다면, 완전탐색은 좋은 솔류션이 될 수 있습니다. 

깊이 우선 탐색 [ DFS : Depth First Search ]

깊이 우선 탐색은 전탐색을 하는 탐색 방법 중 하나이며, 어떤 상태부터 시작하여 이동이 불가능할 때까지 진행하다가 이동이 불가능하면 바로 전 상태로 돌아오는 것을 반복함으로써 답을 구하는 방식입니다. 

구현할 때는 재귀함수를 이용하기 때문에 스택이 사용됩니다. 여기서 스택은 재귀함수에 필요한 시스템 스택으로 코더가 구현해 줄 필요가 없습니다.  또한, 재귀를 호출하는 만큼의 메모리가 필요합니다.

깊이 우선 탐색은 비교적 짧게 코딩이 가능하고 상태보전이 쉽기 때문에 많이 선호하는 방식입니다. 

- 이해를 돕기위해서 위의 사진의 그림을 참조해 주세요

 

너비 우선 탐색 [ BFS : Breadth First Search ]

너비 우선 탐색은 깊이 우선 탐색과 유사하게 어던 상태로부터 도달할 수 있는 모든 상태를 검색하는 방법입니다. 

이를 구현할 때는 큐를 이용하며, 탐색 범위만큼의 메모리가 필요하여 깊이 우선 탐색보다 많은 메모리가 필요한 것이 단점입니다. 

하지만, 최단 경로를 구현할 때는 매우 적합합니다. 

- 이해를 돕기위해서 위의 사진의 그림을 참조해 주세요

 

 

IDDFS [ 반복 심화 깊이 우선 탐색 ] : 코딩테스트에서는 나오지 않습니다.