인프런 커뮤니티 질문&답변

안녕하세요, 인프런 AI 인턴입니다. Al Al님. 좋은 질문 감사드립니다. 😊

BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 동작 원리를 이해하면 질문하신 부분에 대한 이유를 알 수 있습니다.

BFS의 동작 원리

• BFS는 큐(Queue) 자료구조를 활용하여 시작 노드로부터 가까운 노드부터 차례대로 탐색합니다. 이는 먼저 들어온 노드를 먼저 처리하는 FIFO(First In, First Out) 원칙에 따라 이루어집니다.
  

왜 큐에서 pop할 때 출력하는가?

1. 탐색 순서: BFS는 큐에 담긴 노드를 방문할 때 탐색합니다. 탐색의 의미는 해당 노드에 도달하여 작업을 수행하는 순간이며, 이때를 기준으로 출력하는 것이 논리적으로 맞습니다.

2. 탐색의 불변성 유지: queue.append(i)는 그저 노드 i를 방문 계획에 넣는 것이지 방문한 것이 아닙니다. 실제로 방문했을 때(즉, 큐에서 꺼냈을 때) 탐색을 완료하고, 방문했다는 것을 기록하거나 출력을 해야 합니다.

3. 동기화: 큐에서 노드를 꺼낼 때(pop) 비로소 해당 노드가 ‘방문 완료’ 상태가 됩니다. 즉, 출력도 이론적으로 완료된 시점에 맞추는 것이 타당합니다. 기본적인 컴퓨팅 원칙에 맞도록 동작하기 때문에 큐에서 pop할 때 노드를 처리하는 것이 자연스럽습니다.

BFS에 대한 더 많은 정보는 다음의 유사한 문제들을 참고해보세요:
- 질문1: (백준 1260) 큐 사용과 BFS와 DFS 차이
- 질문2: BFS에서 큐와 방문 처리

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.