2005학년도 수능 예비평가 (이산수학) 30번

한 인터넷 회사에서는 마을 A, B, C, D, E를 연결하는 광케이블을 도로를 따라 매설하려고 한다. 아래 그래프는 각 마을을 꼭지점으로 나타내고, 두 마을 사이에 도로가 있을 때 해당하는 꼭지점을 변으로 연결한 다음, 광케이블 매설비용을 변에 부여하여 그린 것이다. 다섯 마을을 연결하는 광케이블을 매설하는 데 드는 최소 비용은 백만원이다. 이때, 에 알맞은 수를 구하시오. [4점]

(단위 : 백만원)

최단경로(shortest-path)를 구하는 문제입니다. 그래프에서 각 변에 지정된 값의 합이 최소 또는 최대가 되는 경로를 최적의 경로(optimal path)라고 합니다. ^^

풀이보기

(답) 201

그래프에서 최단경로를 찾을 때, 생성수형도가 만들어질 때까지, 다음 과정을 반복합니다.

i) 가장 큰 값을 갖는 변을 제거한다.
ii) 같은 값을 갖는 변을 제거한다.

그림에서 45+50+52+54 = 201 ^^