✓

태그:

29. 최소 신장 트리 CLASS 5

별의 거리 = 간선의 가중치

풀이 비스무리한거 보기

모든 별을 이용해서 별자리를 만드는 경우 중 그 길이가 가장 짧은 경우의 길이를 구하는 문제입니다. 이 경우는 MST를 구해야 하지만 그래프가 주어지지 않은 경우입니다. 대신 점 사이의 거리를 그래프의 간선의 가중치로 사용하겠다고 했으므로 각 점쌍에 대하여 거리를 구합니다. 즉, n개의 점에 대한 완전 그래프를 생성합니다. 이 그래프에서 MST를 만든 후, 그 가중치의 합을 출력하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-06 14:41:25

---