🌟자료 구조를 이용한 탐색 알고리즘

• 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미
• 대표적인 탐색 알고리즘 : DFS, BFS
  그래프탐색, 완전탐색

깊이 우선 탐색(DFS, Depth-First Search)

• 깊이 우선 탐색 : 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동 ( 아래 -> 옆)

• 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 -> 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리 그리고 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼내기 (두 번째 과정을 더 이상 수행할 수 없을 때까지 반복)

• LIFO 스택(stack)으로 구현, 재귀 함수로 구현 : 스택은 내림차순, 재귀는 오름차순

• ex) 미로찾기, 퍼즐해결, 그래프의 모든노드 방문 알고리즘 문제 등에 활용

• BFS에 비해 메모리 사용량이 적을 수 있음

  

  너비 우선 탐색(BFS, Breadth-First Search)

• 너비 우선 탐색 : 최대한 넓게 이동한 다음, 더 이상 갈 곳이 없을 경우 아래로 이동 ( 옆 -> 아래 )

• 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 -> 2. 큐에서 노드를 꺼내 해당 노드이 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 (두 번째 과정을 더 이상 수행할 수 없을 때까지 반복)

• FIFO 큐(queue)를 이용하여 구현

• ex) 최단 경로찾기, 네트워크 탐색, 그래프의 레벨 순회 등에 알고리즘 문제에 활용

• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용 : DFS 사용시 처음으로 발견되는 답이 최단거리가 아닐 수 있어서 다 구한 후 비교해야하지만 BFS는 현재 노드에서 가까운 곳 부터 찾기 때문에 먼저 찾아지는 해답이 최단거리여서