다음 방향 그래프(directed graph)에서 노드 A부터 시작하여… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 24년 1회차
다음 방향 그래프(directed graph)에서 노드 A부터 시작하여 깊이 우선 탐색과 너비 우선 탐색을 수행하는 경우, 여섯 번째로 방문하는 노드의 쌍을 바르게 연결한 것은? (단, 노드 A는 첫 번째 방문 노드이고, 인접 노드가 다수일 경우 방문 순서는 알파벳순으로 하며, 탐색 과정에서 도달하지 못하는 경로는 고려하지 않는다)
1
C / D
2
D / I
3
H / H
4
I / H
해설
여섯 번째 방문 노드는 깊이 우선 탐색이 I, 너비 우선 탐색이 H이다.
그래프의 간선은 A→B, A→D, B→G, C→A, C→H, D→I, E→C, E→F, F→B, G→H, I→H이며, A에서 도달 가능한 노드는 A, B, D, G, H, I뿐이다.
깊이 우선 탐색: A → B → G → H까지 내려간 뒤 되돌아와 D → I 순이므로 A, B, G, H, D, I.
너비 우선 탐색: A의 인접 B, D, 다음 단계로 B의 G와 D의 I, 마지막으로 H이므로 A, B, D, G, I, H.
- C를 여섯 번째로 보는 경우: C로 들어오는 간선은 E→C뿐이라 A에서 C에 도달할 수 없다.
- 깊이 우선에서 D를 여섯 번째로 보는 경우: D는 다섯 번째로 방문된다.
- 깊이 우선에서 H를 여섯 번째로 보는 경우: H는 G 다음 네 번째로 방문된다.
오류나 개정된 내용이 보이면 알려주세요