다음 행렬은 일곱 개의 정점(vertex)을 갖는 그래프의 간선(edg… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
다음 행렬은 일곱 개의 정점(vertex)을 갖는 그래프의 간선(edge)들 간의 거리를 나타낸다. Dijkstra 알고리즘을 적용하여 정점 A로부터 나머지 정점들까지 최단경로를 찾을 때, 이에 해당하는 정점의 순서는? (단, ∞는 두 정점 간에 해당 간선이 없다)
ABCDEFG
A049∞∞∞∞
B40410∞∞∞
C940∞8∞1
D∞10∞025∞
E∞∞820∞6
F∞∞∞5∞03
G∞∞1∞630
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)보다 먼저 확정해 틀리다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 12년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기