참고 자료
https://covenant.tistory.com/132
✨핵심 Point
- 최단 거리 문제를 푼다면 BFS를 사용합니다.
- 이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS로 구현하는 것이 좋습니다.
시간 복잡도
- 인접 리스트 : O(N+E)
- 인접 행렬 : O(N²)
DFS(Depth First Search)
👍루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식.
DFS는 깊이 우선 탐색(Depth First Search)로 탐색 공간이 제한되어있고 , 탐색 공간 내 탐색 목표가 있는지 검사 할때 유용하게 사용됩니다.
DFS는 이러한 재귀 특성 때문에 탐색 공간의 깊이가 제한되어 있지 않은 문제에서는 적용하기 힘듭니다.
중복 검사가 필요한지 항상 체크해야 합니다.
- Stack 사용
- 재귀함수 사용
BFS(Breadth-First Search)
👍루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
DFS와 달리 탐색 공간이 아무리 깊더라도 가능. 목표상태만 존재한다면 찾을 수 있으나 시간복잡도를 잘 따져보아야 합니다.
Hi!