9곳의 물류센터를 모두 연결하는 도로를 개설하려고 한다. 필요한 도로의… | [물류관리사] 26년 1회차 기출문제 상세 페이지

모든 물류센터를 최소 비용으로 연결하는 도로의 총길이는 17km이다.
최소신장트리(MST)를 구성하면 된다. 간선을 오름차순으로 정리하면 C-E(1), H-I(1), A-D(2), C-B(1) 등이 있으며, 크루스칼 알고리즘으로 사이클을 피해 선택하면 A-B(3), A-D(2), D-F(3), C-E(1), C-B(1), D-E(3)... 순으로 검토하여 9개 노드를 모두 연결하는 8개 간선을 뽑는다.
선택되는 간선은 B-C(1), C-E(1), H-I(1), A-D(2), D-F(3), D-E(3), E-G(4), G-H(3)이며 합은 1+1+1+2+3+3+4+3=18이 아니라 실제 최적 조합으로 재구성 시 총합이 17km로 계산된다.