개요

• DFS나 BFS, 둘 다 모든 노드를 순회하는 탐색 방법이다.
• 완전탐색이 목표라면 둘 중 어떠한 방법을 선택해도 무방할 것이다.
• 개인적으로는 좀 더 직관적이게 다가오는 게 DFS라 완전탐색이 필요할 땐 DFS를 사용하고
• 최단 경로나 임의의 경로를 찾아야하는 경우에만 BFS를 사용한다.
• 두 경우 모두 방문한 노드(visited)에 대한 관리가 매우 중요하다.
• visited의 유무에 따라 무한루프에 빠지느냐 그렇지 않느냐가 결정 되는 경우가 비일비재하다.

DFS (Depth-First-Search)

• 깊이 우선
  • 더 깊어지지 못하는 그 순간까지 우선 들어가고 본다. (visited 아닐 시)
• 방향 우선
  • 어떠한 방향으로 더 들어가지 못하는 그 순간까지 우선 들어가고 본다. (visited 아닐 시)
• 재귀 호출 사용
  • 더 깊어질 수 있는 newNode를 발견한 순간 그 newNode에서 즉시 또 탐색을 진행하면 되기에 재귀 호출이 적합하다.
  • 무한루프에 빠지지 않도록 재귀 탈출 조건을 명확히 써줘야한다.
  • 방문 이력인 visited를 체크해주지 않는다면 왔던 길을 계속 왔다 갔다 하는 일이 발생하여 유쾌하지 않은 상황이 발생한다.

BFS (Breadth-First-Search)

• 너비 우선
  • 현재 노드와 인접한 모든 경우는 우선 다 queue에 넣고 본다. (visited 아닐 시)
• 거리 우선
  • 현재 노드에서 단 한칸의 거리만 떨어져 있는 경우는 우선 다 queue에 넣고 본다. (visited 아닐 시)
• queue 자료구조를 사용
  • 만약 재귀를 사용하여 인접한 newNode를 발견한 순간 그 newNode에 들어간다면 너비(거리)의 우선이 보장되지 않는다.
  • 너비(거리)의 보장을 위해 newNode 발견 시 queue에 등록을 한 다음, queue.front()에 있는 노드만으로 탐색을 진행한다.
  • queue.front()를 통한 탐색이 완료 됐을 시 queue.pop()을 진행하며 queue.empty()가 될 때까지 이를 반복한다.
  • 방문 이력인 visited를 체크해주지 않는다면 왔던 길을 계속 왔다 갔다 하는 일이 발생하여 유쾌하지 않은 상황이 발생한다.

최단 경로 찾기에는 BFS가 더 적합, Why?

• DFS로 탐색을 할 경우, 모든 경로를 뒤져보지 않는 한 어떠한 값이 최소라는 보장이 불가능
• 아무리 작은 수라 할지라도 마지막 경우에서 더 작은 경우가 있을 수도 있기 때문에 !
• 그에 반해 BFS로 탐색을 하게 되면, 경로의 길이가 1인 경우부터 차근차근 탐색하기 때문에 적합한 답이 발견되는 순간 최단 경로라는 보장이 가능
• 아직도 탐색이 진행되고 있다는 사실 자체가 답이 아직 발견되지 않았다는 뜻이기에 발견된 순간 그 값이 최소라는 보장이 가능

개인적으로는 완전탐색 시 DFS가 더 편하다, Why?

• DFS,BFS 모두 완전탐색에 적합하다.
• BFS는 queue를 관리해야하고, DFS에 비해 고려해야할 사항이 더 많다고 느껴진다.
• 하지만 DFS는 visited와 재귀 탈출 조건만 잘 관리해준다면 손쉽게 완전탐색이 가능해서 편하다.