다음 행렬은 일곱 개의 정점(vertex)을 갖는 그래프의 간선(edg… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
다음 행렬은 일곱 개의 정점(vertex)을 갖는 그래프의 간선(edge)들 간의 거리를 나타낸다. Dijkstra 알고리즘을 적용하여 정점 A로부터 나머지 정점들까지 최단경로를 찾을 때, 이에 해당하는 정점의 순서는? (단, ∞는 두 정점 간에 해당 간선이 없다)
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | 0 | 4 | 9 | ∞ | ∞ | ∞ | ∞ |
| B | 4 | 0 | 4 | 10 | ∞ | ∞ | ∞ |
| C | 9 | 4 | 0 | ∞ | 8 | ∞ | 1 |
| D | ∞ | 10 | ∞ | 0 | 2 | 5 | ∞ |
| E | ∞ | ∞ | 8 | 2 | 0 | ∞ | 6 |
| F | ∞ | ∞ | ∞ | 5 | ∞ | 0 | 3 |
| G | ∞ | ∞ | 1 | ∞ | 6 | 3 | 0 |
1
A→B→C→G→D→E→F
2
A→B→C→G→E→D→F
3
A→B→C→G→E→F→D
4
A→B→C→G→F→D→E
해설
Dijkstra 알고리즘으로 확정되는 정점 순서는 A→B→C→G→F→D→E이다.
매 단계 미확정 정점 중 최소 거리 정점을 확정하고 인접 거리를 갱신한다.
A 확정: B=4, C=9
B(4) 확정: C=min(9, 8)=8, D=14
C(8) 확정: E=16, G=9
G(9) 확정: E=min(16, 15)=15, F=12
F(12) 확정: D=min(14, 17)=14
D(14) 확정: E=min(15, 16)=15
E(15) 확정
- G 다음에 D를 고르는 순서는 F(12)가 D(14)보다 가깝다는 점을 놓친 것이다.
- G 다음 E, D, F 순서는 E(15)보다 F(12)·D(14)가 먼저 확정되어야 하므로 틀리다.
- G 다음 E, F, D 순서도 E(15)를 가장 가까운 F(12)보다 먼저 확정해 틀리다.
오류나 개정된 내용이 보이면 알려주세요