코딩 테스트
[코딩 테스트] DFS, BFS가 각각 스택, 큐를 사용하는 이유
study_memo
2024. 1. 12. 20:37
DFS - 갈 수 있을 만큼 깊이 간 후, 갈 곳이 없으면 이전 정점으로 돌아감
<스택, 재귀함수 이용>
DFS는 방문 순서를 스택으로 관리한다.
스택을 쓰는 이유는, dfs 안에서 다시 dfs 함수를 호출하는 재귀 호출을 하기 때문이다.
함수 호출은 시스템 스택에서 관리한다. ( -> 다시 말해, 스택을 특별히 정의하지 않아도 사용할 수 있다.)
BFS - 시작점에서 가까운 정점 순서대로 탐색
<큐 이용>
큐를 이용하는 BFS는 명시적으로 큐를 정의해줘야 한다.
먼저 방문된 순서대로 다시 방문을 진행해야 하기 때문에, 선입선출형 자료구조인 큐가 적합하다.