2018 7급 국가직 기출풀이 - 자료구조론 마형 8번

문제 풀이에 앞서,

틀린 부분이 많이 있을 수 있습니다.

피드백을 받으면 글 수정하겠습니다. 소통이 큰 힘이 됩니다. 감사합니다.

---

문제

문8. 다음 인접 행렬은 5개 도시 간의 직접 거리를 보여준다. 인천-대구 구간 최단 경로 거리와 광주-대구 구간 최단 경로 거리 사이의 차이 값은? (단, ∞는 두 도시 간에 직접적인 연결이 없음을 의미한다.)

	대전	광주	서울	인천	대구
대전	0	10	15	25	9
광주	10	0	18	20	∞
서울	15	18	0	3	17
인천	25	20	3	0	∞
대구	9	∞	17	∞	0

① 1

② 2

③ 3

④ 4

---

정답

①번

---

풀이전 기초

이번엔 따로 없습니다.

---

풀이과정

1. 인천-대구 최단 경로 거리 (직항없음)

1) 서울 경유 : 3(인천-서울 거리) + 17(서울-대구 거리) = 20

2) 대전 경유 : 25(인천-대전 거리) + 9(대구-대전 거리) = 34

3) 인천 경유 불가 -> 대구와의 연결 없음

∴ 인천 - 대구 최단 경로 거리 : 20

 

2. 광주-대구 최단 경로 거리 (직항 없음)

1) 대전 경유 : 10 + 9 = 19

2) 서울 경유 : 18 + 17 = 35

3) 인천 경유 불가 -> 대구와의 연결 없음

∴ 광주 - 대구 최단 경로 거리 : 19

---

문제의 최단 경로 구간 거리 사이의 차 = 20 - 19 = 1

따라서 1번이 정답

---

마지며...

이번엔 자료구조론 문제라기 보다는 수학문제를 푸는 느낌에 가까웠습니다.

문제풀이와 구현화 과정이 다름에 감사를 느끼고 있습니다.ㅠㅠ