다음 인접 행렬은 5개 도시 간의 직접 거리를 보여준다. 인천-대구 구… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 18년 1회차
다음 인접 행렬은 5개 도시 간의 직접 거리를 보여준다. 인천-대구 구간 최단 경로 거리와 광주-대구 구간 최단 경로 거리 사이의 차이 값은? (단, ∞는 두 도시 간에 직접적인 연결이 없음을 의미한다)
| 대전 | 광주 | 서울 | 인천 | 대구 | |
|---|---|---|---|---|---|
| 대전 | 0 | 10 | 15 | 25 | 9 |
| 광주 | 10 | 0 | 18 | 20 | ∞ |
| 서울 | 15 | 18 | 0 | 3 | 17 |
| 인천 | 25 | 20 | 3 | 0 | ∞ |
| 대구 | 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이다.
오류나 개정된 내용이 보이면 알려주세요