다음 그래프에서 정점 A부터 너비 우선 탐색(BFS, breadth f… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
다음 그래프에서 정점 A부터 너비 우선 탐색(BFS, breadth first search)을 사용하여 나올 수 있는 결과로 옳지 않은 것은?
1
A B C D E F
2
A C B D F E
3
A C F B E D
4
A D C B F E
해설
너비 우선 탐색은 같은 깊이의 정점을 모두 방문한 뒤 다음 깊이로 내려가므로, A C F B E D는 나올 수 없는 결과이다.
A와 인접한 B·C·D를 모두 방문하기 전에 깊이 2인 F를 방문했기 때문이다. 또한 깊이 2의 순서는 깊이 1에서 부모가 큐에 들어간 순서를 따라야 한다.
- A B C D E F: B·C·D 순으로 방문했으므로 B의 자식 E, C의 자식 F 순서가 맞다.
- A C B D F E: C·B·D 순으로 방문했으므로 C의 자식 F가 B의 자식 E보다 먼저 온다.
- A D C B F E: D·C·B 순으로 방문했으므로 F, E 순서가 맞다.
오류나 개정된 내용이 보이면 알려주세요