[코딩 테스트] DFS, BFS가 각각 스택, 큐를 사용하는 이유

DFS - 갈 수 있을 만큼 깊이 간 후, 갈 곳이 없으면 이전 정점으로 돌아감

 <스택, 재귀함수 이용>

DFS는 방문 순서를 스택으로 관리한다.

스택을 쓰는 이유는, dfs 안에서 다시 dfs 함수를 호출하는 재귀 호출을 하기 때문이다.

함수 호출은 시스템 스택에서 관리한다.  ( ->  다시 말해, 스택을 특별히 정의하지 않아도 사용할 수 있다.)

---

BFS - 시작점에서 가까운 정점 순서대로 탐색

 <큐 이용>

큐를 이용하는 BFS는 명시적으로 큐를 정의해줘야 한다.

먼저 방문된 순서대로 다시 방문을 진행해야 하기 때문에, 선입선출형 자료구조인 큐가 적합하다.