BFS 탐색 방식
간선 가중치가 모두 같을 때 최단 거리 계산에 어울립니다.
그래프 탐색은 자료구조 선택이 방문 순서를 바꾼다
BFS 큐, 반복 DFS 스택, visited, 거리 배열은 같은 그래프에서도 서로 다른 질문에 답합니다.
DFS 탐색 방식
재귀 대신 명시 스택을 쓰면 호출 깊이 위험을 줄일 수 있습니다.
BFS 방문 표시 시점
넣을 때 표시할지 꺼낼 때 표시할지 일관성이 필요합니다.
BFS 거리 배열
도달하지 못한 정점은 별도 값으로 남겨야 합니다.
순회 순서
인접 리스트 정렬과 push 순서가 출력 방문 순서를 바꿉니다.
복잡도
각 정점과 간선을 한 번씩 보는 구조라 O(V+E)가 기본입니다.
경로 복원
부모 배열을 함께 저장하면 최단 경로 자체를 되짚을 수
있습니다.