신도시 A지역에 지역도로를 신설하려고 한다. 6곳의 거점 중 어디에서나… | [물류관리사] 14년 1회차 기출문제 상세 페이지

모든 거점을 연결하는 최소신장나무(MST)를 구성하면 최소 총비용은 170억원이다.
그림의 간선 비용은 1-2가 15, 1-3이 50, 1-4가 70, 1-5가 90, 2-3이 60, 2-4가 45, 2-5가 30, 3-6이 100, 4-5가 80, 4-6이 30이다. 6개 거점이 서로 직접 또는 경유해 닿기만 하면 되므로 순환이 없는 5개의 도로만 건설하면 충분하다.
싼 간선부터 순환이 생기지 않도록 골라 나가면 1-2(15) → 2-5(30) → 4-6(30) → 2-4(45) → 1-3(50) 순으로 채택되고, 이 시점에 6개 거점이 모두 하나로 이어진다.
총비용은 $15+30+30+45+50 = 170$억원이다. 채택하지 않은 1-3 대체 간선인 2-3(60)이나 4-6 대신 쓸 3-6(100), 4-5(80) 등은 모두 더 비싸므로 170억원보다 낮은 조합은 존재하지 않는다.