BFS & DFS

BFS - Breadth-First Search

• 시작점에서 인접한 점들을 먼저 탐색하는 방법
• 두 점 사이의 최단 경로 or 임의의 경로를 찾고 싶을 때 사용
• recursive하게 동작하지 않는다.
• 어떤 점들을 방문했었는지 여부를 반드시 검사해야 한다.
• 방문한 점들을 차례로 저장한 후 꺼낼 수 있는 Queue 사용하는게 좋음
• 시간 복잡도
  • 인접 리스트로 표현된 그래프: $O(N+E)$
  • 인접 행렬로 표현된 그래프: $O(N^2)$

DFS - Depth-First Search

• 시작점에서 인접한 점들 중 하나를 골라 해당 점으로 계속 들어가는 것.
• 모든 점들을 방문할 때 사용 ex) 미로 탐색
• recursive하게 동작
• 어떤 점들을 방문했었는지 여부를 반드시 검사해야 한다.
• recursive를 사용하지 않을꺼면 stack을 사용하는게 좋음
• 시간 복잡도
  • 인접 리스트로 표현된 그래프: $O(N+E)$
  • 인접 행렬로 표현된 그래프: $O(N^2)$

DFS가 BFS에 비해 간단하지만 느리다.

관련 문제
programmers - https://programmers.co.kr/learn/courses/30/parts/12421