다음 인접 행렬은 도시 간의 경로 값들을 나타낸 것이다. 서울에서 안양… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 11년 1회차
다음 인접 행렬은 도시 간의 경로 값들을 나타낸 것이다. 서울에서 안양, 서울에서 인천, 서울에서 수원, 서울에서 대전까지 각각 최단 경로 값들을 구하고자 한다. 각각 최단 경로 값들의 합으로 옳은 것은? (단, ∞는 두 도시 간의 연결이 없음을 의미한다)
| 서울 | 안양 | 인천 | 수원 | 대전 | |
|---|---|---|---|---|---|
| 서울 | 0 | 10 | 20 | 25 | ∞ |
| 안양 | 10 | 0 | 15 | 13 | ∞ |
| 인천 | 20 | 15 | 0 | 20 | 40 |
| 수원 | 25 | 13 | 20 | 0 | 30 |
| 대전 | ∞ | ∞ | 40 | 30 | 0 |
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
- 직행 거리만 더하거나 일부 경유를 빠뜨리면 다른 값이 나오므로, 경유 경로를 모두 비교해야 한다.
- 대전은 서울과 직접 연결이 없으므로 반드시 인천 또는 수원을 거친 값 중 작은 것을 택한다.
오류나 개정된 내용이 보이면 알려주세요