[C++] 탐색 - 브루트 포스(brute force) 전체 탐색

• brute force(무식한 힘, 전체탐색) 문제로 완전탐색 알고리즘이다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
• 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.
• 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
• 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.

 

<너비 우선 탐색(BFS, Breadth-first search)>

  - 그래프에서 완전탐색 방법 중 하나

  - 탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 횡방향으로 탐색을 진행해 나가는 방식

 

장점:

  - 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점:

  - 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 한다.

  - 해가 존재하지 않는다면 유한(finite) 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.

  - 무한(infinite) 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.