같은 그래프
그래프가 같아도 큐와 스택 중 무엇을 쓰느냐에 따라 “먼저 확정되는 값”이 달라진다.
BFS / DFS
먼저 “거리”인지 “구조”인지 결정한다
BFS와 DFS는 같은 그래프를 보더라도 처리 순서가 다르다. 무가중치 최단 거리는 BFS, 경로 추적과 구조 확인은 DFS가 기본 선택이다.
Queue가까운 정점부터 레벨 처리
Stack한 경로를 깊게 따라감
Visit넣기 전에 방문 표시
BFS
queue
거리 순서로 확장
시작점에서 가까운 레벨을 먼저 처리하므로 무가중치 최단 거리의 기본 템플릿이 된다.
1→2→3→4→5
DFS
stack / recursion
경로를 끝까지 추적
한 갈래를 깊게 내려가므로 경로 존재, 사이클, 연결 구조를 확인할 때 흐름이 자연스럽다.
1→2→4→3→5
문제 목표
거리면 BFS, 구조와 경로면 DFS를 먼저 떠올린다.
방문 체크
큐나 스택에 넣기 전에 표시해야 중복 삽입을 줄인다.
복잡도
정점과 간선을 한 번씩 보면 시간 복잡도는 O(V + E)다.