산업단지 내에 있는 6개의 물류거점을 모두 연결하는 도로를 신설하려고 … | [물류관리사] 19년 1회차 기출문제 상세 페이지
1[물류관리사] 19년 1회차
산업단지 내에 있는 6개의 물류거점을 모두 연결하는 도로를 신설하려고 한다. 총도로연장을 최소화할 경우에 필요한 도로연장은? (단, 다음은 각 링크의 출발지 물류거점, 도착지 물류거점, 해당 링크연장을 나타내고 ‘0’은 해당 링크가 없음을 나타냄)
(단위: km)
| 출발지＼도착지 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 3 | 5 | 4 | 5 | 0 |
| B | 3 | 0 | 6 | 5 | 0 | 0 |
| C | 5 | 6 | 0 | 4 | 3 | 5 |
| D | 4 | 5 | 4 | 0 | 2 | 4 |
| E | 5 | 0 | 3 | 2 | 0 | 3 |
| F | 0 | 0 | 5 | 4 | 3 | 0 |
1
14 km
2
15 km
3
16 km
4
17 km
5
18 km
해설
6개 거점을 모두 연결하면서 총연장을 최소화하면 15 km가 된다. 이는 최소걸침나무(최소비용 신장수) 문제로, 순환이 생기지 않도록 짧은 링크부터 5개를 고르면 된다.
링크를 짧은 순으로 보면 D-E 2, A-B 3, C-E 3, E-F 3, A-D 4, C-D 4, D-F 4, A-C 5, B-D 5, C-F 5, B-C 6이다. 순환을 만들지 않는 것만 차례로 채택하면 D-E(2) → A-B(3) → C-E(3) → E-F(3) → A-D(4) 다섯 개가 선택된다.
이 다섯 링크로 C-E-D-F가 이어지고 A-D가 A와 B를 그 묶음에 연결하므로 6개 거점이 모두 통한다. 총연장은 2+3+3+3+4 = 15 km이다.
거점이 6개면 필요한 링크는 n-1인 5개뿐이며, C-D 4나 D-F 4처럼 길이가 같아도 이미 연결된 거점을 다시 잇는 링크는 순환을 만들어 제외된다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.