정보올림피아드 초등 - 지역예선] 2009년도 5번문제

 

5.도시공사에서는 A, B, C, D, E의 5개 아파트 단지를 연결하는 도로를 놓으려고 한다. 여기서 A단지와 B단지가 연결되고 또 B단지와 C단지가 연결되면 A단지와 C단지도 연결된 것이다. 각 단지를 직접 연결하는데 드는 비용이 아래 표와 같다면, 5개 단지를 연결하는 데 드는 가장 적은 비용은 얼마인가?   A B C D E A   8 12 6 19 B 8   18 16 7 C 12 18   17 11 D 6 16 17   10 E 19 7 11 10   ①31 ②32 ③33 ④34 ⑤36

풀이) A-B-C-D-E 의 5개 단지를 최소의 비용으로 연결하는 것이므로

각각의 단지에서 가장 적은 비용으로 연결 되는 단지를 찾아 본다.

A - D : 6

B - E : 7

C - E : 11

D - A : 6

E - B : 7

연결을 해 보면 A-D,B-E-C 로 연결이 가능 한데 두구간이 끊어져 있으므로 두구간을 연결하는 가장 최소의 비용은 A-B 가 8 이므로 D-A-B-E-C 로 연결을 하면 최소의 비용이 나온다.

따라서 이렇게 연결 하는 비용은 6 + 8 + 7 + 11 = 32

정답) 2번