백준 1260 (DFS 와 BFS) 프린트 위치 질문
안녕하세요 🙂
bfs 에서 질문이 있는데 왜 프린트(print(idx, end = ' ')를 for loop 안에서 queue.append(i) 한 다음 프린트하지 않고 큐에서 팝할때 프린트 하나요?
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. Al Al님. 좋은 질문 감사드립니다. 😊
BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 동작 원리를 이해하면 질문하신 부분에 대한 이유를 알 수 있습니다.
BFS의 동작 원리
- BFS는 큐(Queue) 자료구조를 활용하여 시작 노드로부터 가까운 노드부터 차례대로 탐색합니다. 이는 먼저 들어온 노드를 먼저 처리하는 FIFO(First In, First Out) 원칙에 따라 이루어집니다.
왜 큐에서 pop할 때 출력하는가?
탐색 순서: BFS는 큐에 담긴 노드를 방문할 때 탐색합니다. 탐색의 의미는 해당 노드에 도달하여 작업을 수행하는 순간이며, 이때를 기준으로 출력하는 것이 논리적으로 맞습니다.
탐색의 불변성 유지:
queue.append(i)는 그저 노드 i를 방문 계획에 넣는 것이지 방문한 것이 아닙니다. 실제로 방문했을 때(즉, 큐에서 꺼냈을 때) 탐색을 완료하고, 방문했다는 것을 기록하거나 출력을 해야 합니다.동기화: 큐에서 노드를 꺼낼 때(
pop) 비로소 해당 노드가 ‘방문 완료’ 상태가 됩니다. 즉, 출력도 이론적으로 완료된 시점에 맞추는 것이 타당합니다. 기본적인 컴퓨팅 원칙에 맞도록 동작하기 때문에 큐에서pop할 때 노드를 처리하는 것이 자연스럽습니다.
BFS에 대한 더 많은 정보는 다음의 유사한 문제들을 참고해보세요:
- 질문1: (백준 1260) 큐 사용과 BFS와 DFS 차이
- 질문2: BFS에서 큐와 방문 처리
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
itertools, sys같은 STL을 사용할 수 없는 경우 질문드립니다.(백준 11724)
1
42
1
백준 13565 침투 질문
1
95
2
침투/섬개수 질문
1
139
2
재귀함수 질문
1
146
1
촌수계산(백준 2644) 질문
1
189
2
다른 주제 강의
1
140
2
graph
1
200
1
재귀 함수 Depth
1
184
1
백준 DFS
1
220
1
[바닥장식][런타임에러] 질문 있습니다.
1
296
3
그래프 짤 때 adjacency matrix vs adjacency list
1
396
2
2644문제(촌수 구하기) 질문입니다.
1
255
2
DFS 문제 하나 여쭤봅니다!..
1
299
1
다음강의
1
248
1
알고리즘 수업 - 깊이 우선 탐색 2( 백준 24480) 번 질문
1
287
1
1260 문제 풀이에서는 함수 global로 변수 선언
2
214
1
PyPy3와 Python3
1
334
1
백준 2606
1
218
1
22479번 문제 런타임 에러 도와주세요 ㅠㅠ
1
441
1
11724 문제 질문
1
307
2
그래프 초기화
1
284
1
선생님! 바이러스 문제 코드 질문있어요오
1
279
2
질문있습니다!
1
335
1
2644 촌수계산 문제에 관한 질문
1
243
1