소개글

면접 대비겸 여러 블로그들을 참고하면서 정리해본 CS 지식들을 포스팅하고 있습니다.
만약 틀린 내용이 있다면 피드백은 언제나 환영합니다.
제 나름대로 요약한 내용이기 때문에 자세한 내용은 제일 아래쪽 참고 사이트에서 확인하면 좋을 것 같습니다!
말투는 편한 말투로 작성하니 양해 부탁드립니다.

DFS, BFS

DFS (Depth First Search)

• 깊이 우선 탐색
• 루트노드에서 시작해, 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색
• 찾는 노드가 깊게 있을수록 유리
• 스택 or 재귀로 구현

장점

• 백트래킹 해야하는 노드들만 저장하면 되서 저장공간이 비교적 작아도 됨

단점

• 답이 존재하지 않는 브랜치가 깊다면, 매우 오랜 시간이 걸릴 수 있음
• 찾은 답이 최단경로라는 보장이 없음

BFS (Breadth First Search)

• 너비 우선 탐색
• 루트노드에서 시작해, 인접한 노드를 먼저 탐색
• 찾는 노드가 얕게 있을수록 유리
• 큐로 구현

장점

• 해가 있다면, 반드시 찾을 수 있음
• 답이 여러개인 경우에도 최단 경로임을 보장

단점

• 큐를 이용해 다음 분기의 노드들을 저장해놓기 때문에 큰 저장공간 필요

참고 사이트

https://velog.io/@vagabondms/DFS-vs-BFS