문제 설명
김노드는 글로벌 기업 '구골'의 CEO입니다.
'구골'은 총 n개의 서버를 갖고 있는데, 해당 서버가 모두 동기화되어야 합니다. 한편 각 서버는 다른 서버와 연결되어 있지 않으며, 동기화 가능한 서버 쌍에 대한 정보가 syncs라는 매개변수로 주어집니다.
이때, 김노드가 전체 서버의 동기화를 위해 지급해야 하는 최소 비용을 반환하는 solution 함수를 작성하시오.
만약, 전체 서버를 동기화 할 수 없다면 -1을 반환합니다.
예를 들어 '구골'의 서버 연결 현황이 아래와 같다고 가정합니다.
총 6대의 서버가 있으며, 동기화할 수 있는 서버 쌍은 7쌍으로 이는 간선으로 표기되며, 서로 다른 두 서버를 동기화하는 데 필요한 비용은 간선에 작성된 숫자와 같습니다.
이때, 위 사진과 같이 서버를 동기화하면 최소 비용으로 동기화할 수 있으며 그 비용은 32입니다.
제한 사항
n은 서버의 개수이며 입니다.syncs는 서버 동기화 정보를 포함하며 각 항목은 세 값 [x, y, w]로 구성됩니다:syncs의 길이는 1 이상 500,000 이하입니다.x와y는 1 이상n이하의 자연수로, 동기화할 두 서버의 번호를 나타냅니다.w는 1 이상 10,000 이하의 자연수로, 두 서버를 동기화하는 데 필요한 비용을 나타냅니다.
예시 테스트케이스 설명
| 테스트케이스 번호 | n | syncs | return |
|---|---|---|---|
| 1 | 6 | [[2,4,1],[5,3,5],[1,5,10],[4,6,12],[3,2,8],[5,4,9],[3,4,4]] | 32 |
| 2 | 5 | [[3,2,2],[5,4,6],[5,1,5],[2,4,4]] | 17 |
| 3 | 9 | [[8,5,9],[6,7,2],[9,5,1],[2,3,10],[7,4,6],[4,9,5],[5,7,7],[6,8,8],[4,5,3],[9,7,7],[9,8,2],[8,7,10],[4,6,7],[6,9,1],[6,5,7],[1,2,1]] | -1 |
1번 테스트케이스 설명
- 문제에서 주어진 예시와 동일합니다.
2번 테스트케이스 설명
- 주어진 입력 예시는 트리구조이기 때문에 모든 동기화 비용을 합한 17을 출력합니다.
3번 테스트케이스 설명
- 주어진 입력 예시는 1,2,3 정점과 4,5,6,7,8,9 정점이 서로 연결되어 있지 않아 동기화가 불가능합니다.