<보기>의 그래프에 대해 다익스트라(Dijkstra) 알고리… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
<보기>의 그래프에 대해 다익스트라(Dijkstra) 알고리즘을 이용하여 정점 A에서 다른 모든 정점까지의 최단 경로를 찾으려고 한다. 마지막으로 최단 경로를 찾게 되는 정점으로 가장 옳은 것은? (단, 방문할 수 있는 정점이 둘 이상인 경우, 알파벳 순으로 방문한다.)
<보기>
문제 이미지
1
C
2
D
3
H
4
I
해설

마지막으로 최단 경로가 확정되는 정점은 C이다.

A에서 시작해 거리가 가장 작은 정점부터 확정하면 F(3), G(4), J(4), E(5), I(6), B(7), D(7), H(7), C(11) 순이다. G와 J, B·D·H처럼 거리가 같으면 알파벳 순으로 방문한다.

C까지의 최단 거리는 A→B→C(7+4)와 A→G→E→C(4+1+6)가 모두 11로, 나머지 정점의 최단 거리(모두 7 이하)보다 크다.

  • D: A→G→E→D(4+1+2)로 거리 7에 확정되어 C보다 먼저 처리된다.
  • H: A→G→H(4+3)로 거리 7이며, 같은 거리의 B·D 다음에 확정된다.
  • I: A→G→E→I(4+1+1)로 거리 6에 일찍 확정된다.

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

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기