다음 인접 행렬은 도시 간의 경로 값들을 나타낸 것이다. 서울에서 안양… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 11년 1회차
다음 인접 행렬은 도시 간의 경로 값들을 나타낸 것이다. 서울에서 안양, 서울에서 인천, 서울에서 수원, 서울에서 대전까지 각각 최단 경로 값들을 구하고자 한다. 각각 최단 경로 값들의 합으로 옳은 것은? (단, ∞는 두 도시 간의 연결이 없음을 의미한다)
서울안양인천수원대전
서울0102025∞
안양1001513∞
인천201502040
수원251320030
대전∞∞40300
1
66
2
85
3
106
4
110
해설

서울에서 각 도시까지의 최단 경로 값의 합은 106이다.

안양: 직행 10
인천: 직행 20 (안양 경유는 10+15=25)
수원: 안양 경유 10+13=23 (직행 25보다 짧음)
대전: 수원 경유 23+30=53 (인천 경유는 20+40=60)

합계: 10+20+23+53=106

  • 직행 거리만 더하거나 일부 경유를 빠뜨리면 다른 값이 나오므로, 경유 경로를 모두 비교해야 한다.
  • 대전은 서울과 직접 연결이 없으므로 반드시 인천 또는 수원을 거친 값 중 작은 것을 택한다.

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

이어서 풀어보기

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