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

8곳의 물류센터를 모두 연결하는 데 필요한 도로의 최소 길이는 23km이다.
모든 지점을 잇되 순환이 생기지 않게 하는 최소걸침나무 문제이므로, 짧은 구간부터 차례로 고르되 양 끝이 이미 연결된 구간만 건너뛰면 된다. 지점이 8곳이므로 필요한 도로는 7개다.
E-H 2 → F-H 2 → E-G 3 → C-E 3 → A-D 4 → B-E 4 → B-D 5
합계 = 2 + 2 + 3 + 3 + 4 + 4 + 5 = 23km
여기서 B-D 5가 A·D 묶음과 나머지 전체를 이어 주면서 7개 도로가 채워지므로, 남은 A-B 6, D-E 6, C-F 6, G-H 6, A-E 7, B-C 7, D-G 7, E-F 8, B-F 9 구간은 모두 순환을 만들 뿐이라 제외된다.