SWEA 26504 - MST 만들기 [Java]

문제

SW Expert Academy

풀이

이 문제에서는 MST 알고리즘을 구현할 필요는 없지만, MST의 특성에 대해 알고 있어야 풀 수 있는 문제다. 아래는 Kruskal 알고리즘을 기준으로 푼 코드다.

 

일반적으로 Kruskal 알고리즘은 다음과 같은 순서로 진행된다.

1. 가중치 배열 오름차순 정렬
2. Union-Find: 다른 그룹의 노드를 잇는 간선을 선택 → V-1회 반복

가중치의 합이 최소가 되게 하는 MST의 특성 때문에 무조건 가장 큰 가중치를 가져올 수 는 없다.

 

우선 최소 비용(minCost)의 경우는 쉽다. 같은 그룹끼리 선택하는 경우가 없도록 제일 작은 가중치들만 고르도록 하면 된다. 즉, 오름차순으로 정렬된 배열에서 0부터 V-2번째 인덱스까지의 가중치의 합이 된다.

 

최대 비용(maxCost)의 경우, 최대한 중간중간에 같은 그룹의 노드 2개를 선택하는 뻘짓을 섞어야 한다. 시뮬레이션 결과 아래와 같은 규칙성을 발견할 수 있었다.

3 + 5 + 8 = 16

1 + 2 + 3 + 6 = 12

 

파란색을 보면 n번째 간선을 선택한 경우 배열 상에서 인덱스를 n만큼 건너뛰는 것을 확인할 수 있다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			int N = sc.nextInt(); // V = N
			int M = N * (N-1) / 2;
			List<Long> wList = new ArrayList<>();
			for (int i = 0; i < M; i++) {
				wList.add(sc.nextLong());
			}
			Collections.sort(wList);
			
			long minCost = 0;
			for (int i = 0; i < N-1; i++) {
				minCost += wList.get(i);
			}
			
			long maxCost = 0;
			int level = 0;
			int idx = 0;
			while (level < N-1) {
				maxCost += wList.get(idx);
				level++;
				idx += level;
			}
			System.out.println(minCost + " " + maxCost);
		}
		sc.close();
	}
}