75.산업단지 내에 있는 6개의 물류거점을 모두 연결하는 도로를 신설하려고 한다. 총도로연장을 최소화할 경우에 필요한 도로연장은? (단, 다음은 각 링크의 출발지 물류거점, 도착지 물류거점, 해당 링크연장을 나타내고 ‘0’은 해당 링크가 없음을 나타냄)

① 14 km

정답: X

거점 6곳을 잇는 링크 5개를 가장 짧게 골라도 15km라 14km로는 다 이을 수 없다.

② 15 km

정답: O

짧은 링크부터 고리 없이: D-E 2 → A-B 3·C-E 3·E-F 3 → A·B 묶음을 A-D 4로 잇는다(C-D 4·D-F 4는 고리) → 2 + 3 + 3 + 3 + 4 = 15km.

③ 16 km

정답: X

A·B 묶음을 A-D 4 대신 A-C 5나 B-D 5로 이으면 2 + 3 + 3 + 3 + 5 = 16km가 나온다.

④ 17 km

정답: X

고리를 만들지 않고 짧은 것부터 고르면 15km라 17km는 더 긴 링크를 섞은 값이다.

⑤ 18 km

정답: X

링크 5개로 6곳을 잇는 최소 길이는 15km라 18km는 필요 이상으로 길다.