최소비용신장트리 > 문제은행

본문 바로가기


알고리즘 그리디

1060 : 최소비용신장트리

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 1365 회    시도횟수: 3924 회   



정보올림피아드 공부를 더욱 효율적으로 할 수 있도록 전국에 흩어져 있는 정올 학원들을 네트워크로 연결하려고 한다.그러나 모든 학원들을 네트워크로 연결하려면 너무 많은 비용이 필요하기 때문에 정올에서는 학원들을 연결하는 비용을 최소가 되게 하려고 한다. 학원들은연결되어 있는 다른 학원의 회선을 공유할 수 있다.

 

아래 그림과 같이 학원 사이를 연결하기 위한 비용이 주어지면 모든 학원을 연결하기 위한 최소의 비용을 구하는 프로그램을 작성하라.

 

efc6e5f9d670c6da62174cf11a66a8c2_1449722 


첫줄에 학원의 수 N(3≤N≤100)이 주어진다.둘째 줄부터 NxN의 행렬로 100,000이하의 정수가 공백으로 구분되어 입력된다. 행렬의 i j는 i번 학원에서 j번 학원을 연결하기 위한 비용을 나타낸다.



학원들을 모두 연결하기 위한 최소 비용을 출력한다.


[Copy]
5
0 5 10 8 7 
5 0 5 3 6 
10 5 0 1 3 
8 3 1 0 1 
7 6 3 1 0
[Copy]
10


무방향 그래프의 부분그래프이면서 모든 꼭지점을 연결하는 트리를 신장트리라 하며 최소비용으로 구성되는 신장트리를 최소비용신장트리라 한다. 
위 예제에서 1과 2를 연결하는데 5, 2와 4를 연결하는데 3, 3과 4를 연결하는데 1, 4와 5를 연결하는데 1 합계 10의 비용으로 최소비용신장트리를 만들 수 있다.


최소비용신장트리 파일링크



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.