다음 인접 행렬은 5개 도시 간의 직접 거리를 보여준다. 인천-대구 구… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
다음 인접 행렬은 5개 도시 간의 직접 거리를 보여준다. 인천-대구 구간 최단 경로 거리와 광주-대구 구간 최단 경로 거리 사이의 차이 값은? (단, ∞는 두 도시 간에 직접적인 연결이 없음을 의미한다)
대전광주서울인천대구
대전01015259
광주1001820∞
서울15180317
인천252030∞
대구9∞17∞0
1
1
2
2
3
3
4
4
해설

두 최단 경로 거리의 차이는 1이다.

인천-대구는 직접 연결이 없으므로 경유 경로를 비교한다.

  • 인천→서울→대구: 3 + 17 = 20 (최단)
  • 인천→서울→대전→대구: 3 + 15 + 9 = 27
  • 인천→대전→대구: 25 + 9 = 34

광주-대구도 직접 연결이 없으며, 광주→대전→대구 = 10 + 9 = 19가 광주→서울→대구(35) 등보다 짧다.

따라서 차이는 20 − 19 = 1이다.

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

이어서 풀어보기

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