재귀를 쓰지 않고 반복문으로 DFS와 BFS를 구현할 때 핵심 차이점은 무엇인가요?

이렇게 답해 보세요 (핵심 답변)

반복문으로 구현할 때 가장 큰 차이는 탐색 후보를 관리하는 자료구조로 DFS는 명시적 스택(Stack)을, BFS는 큐(Queue)를 사용한다는 점입니다. 시작 정점을 넣고 하나씩 꺼내 인접 정점을 확장하면서 방문 집합(visited)으로 사이클과 중복 탐색을 막으며, 특히 BFS는 큐에 넣는 시점에 방문 표시를 해 중복 삽입을 방지합니다. 인접 리스트에서 각 정점과 간선을 상수 번씩만 처리하면 두 방식 모두 시간 복잡도는 O(V + E)입니다.

함께 설명하면 좋은 이유 (꼬리질문 대비)

1. 가중치가 없는 그래프에서 BFS는 시작점으로부터 간선 수 기준 최단 거리 층(Level) 순서대로 정점을 방문합니다.
2. 재귀 DFS와 똑같은 방문 순서나 후위(Post-order) 복귀 시점 동작이 필요할 때는 스택에 넣는 순서를 조정하거나 진입·복귀 상태를 함께 기록해야 합니다.

면접에서 자주 하는 실수

사이클이 있는 그래프에서 방문 처리를 생략하거나 늦게 표시하면 무한 루프나 메모리 초과가 발생할 수 있습니다.