완전 탐색/DFS/BFS

완전 탐색 (브루트 포스)

• 가능한 모든 경우의 수를 다 시도해 답을 찾는 방법
• 정확하고 확실하게 답을 찾을 수는 있지만, 시간이 오래 걸린다.
• 모든 경우의 수를 구하는 문제 같은 부분에서 많이 사용되는 알고리즘

- 완전 탐색 기법 종류

 

DFS(깊이 우선 탐색)

: 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

 

어떤 노드를 방문했었는지 여부를 반드시 검사 

• 1. 순환 호출 이용(자기 자신을 호출하는순환 알고리즘의 형태)
• 2. 명시적인 스택 사용
  • 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다.

• 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다. 
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

BFS(너비 우선 탐색)

: 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

 

사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다

 

• BFS는 재귀적으로 동작하지 않는다.

• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
  • 즉, 선입선출(FIFO) 원칙으로 탐색
  • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

 

 

 

 

출처: https://github.com/WeareSoft/tech-interview/blob/master/contents/algorithm.md#dfs%EC%99%80-bfs%EC%9D%98-%EC%B0%A8%EC%9D%B4