다음 그래프에서 정점 A부터 깊이 우선 탐색을 수행할 때 가능한 정점들… | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 26년 1회차
다음 그래프에서 정점 A부터 깊이 우선 탐색을 수행할 때 가능한 정점들의 방문 순서로 옳은 것은?
1
A → B → E → F → D → C
2
A → B → D → C → E → F
3
A → D → B → E → F → C
4
A → D → F → E → B → C
해설
가능한 깊이 우선 탐색 순서는 A → D → B → E → F → C이다.
그래프의 간선은 A-B, A-C, A-D, B-D, B-E, D-F, C-F이다. A에서 D, D에서 B, B에서 E로 내려가면 E는 더 갈 곳이 없어 B로, B도 미방문 이웃이 없어 D로 되돌아간다. D의 미방문 이웃 F로 간 뒤 F에서 C를 방문하면 탐색이 끝난다.
- A → B → E → F → D → C: E에서 되돌아간 B에 미방문 이웃 D가 남아 있으므로 D를 방문해야 하며, F는 E·B 어느 쪽과도 인접하지 않다.
- A → B → D → C → E → F: D에는 미방문 이웃 F가 있는데 D와 인접하지 않은 C로 넘어갈 수 없다.
- A → D → F → E → B → C: F의 이웃은 D와 C뿐이므로 F 다음에 E를 방문할 수 없다.
오류나 개정된 내용이 보이면 알려주세요