백준 | 6497번. 전력난 - 최소비용 신장 트리

⬛ 백준 6497번. 전력난 - 최소비용 신장 트리

https://www.acmicpc.net/problem/6497

6497번: 전력난

문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다

💚나의 풀이

• 절약할 수 있는 최대 비용 == 최소 비용으로 사이클 형성 하지 않는 신장트리 형성한 가중치 합을 전체 길의 가중치 합에서 뺀 값이 된다.
• 나머지 로직은 똑같은 최소비용 신장트리의 형태이다.
• 입력받을 때 전체 도로의 가중치를 누적시켜놓고, 이후 사이클을 형성하지 않는 간선들을 N-1개 이어붙일 때의 누적된 가중치 합을 따로 구해서 최소로 사용하는 가중치 합을 전체에서 뺀 값이 답이다.

package to_0906_B;

import java.util.*;

/*6497번. 전력난 - 최소 신장 트리 문풀  */
class Edge implements Comparable<Edge>{
	int s, e, val;
	Edge(int s, int e, int val) {
		this.s=  s;
		this.e= e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int[] parent;
	//find 
	static int find(int a) {
		if(a==parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a!=b) {
			parent[b]= a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		while(true) {//만약에 0 0 입력될 경우 종료 할 거임 
			int m = kb.nextInt();
			int n = kb.nextInt();
			if(m == 0 && n == 0) break;
			
			parent = new int[m];
			for(int i=0; i<m; i++) parent[i] = i;
			
			int sum = 0;//전체 가중치 합을 담을 용도임 
			PriorityQueue<Edge > pQ = new PriorityQueue<>();
			//우선순위 큐에 입력될 애들 담을 거임 
			for(int i=0; i<n; i++) {//길이 n개다
				int a=  kb.nextInt();
				int b= kb.nextInt();
				int c = kb.nextInt();
				pQ.offer(new Edge(a, b, c));
				sum += c;//가중치 합 치기 
			}
			
			int useEdge = 0;//사용 간선 
			int useCost = 0;//연결 최소 가중치 합 담을 용도 
			
			while(useEdge < m-1) { //사용 간선 m-1개 보다 작은 동안 반복 
				Edge cur = pQ.poll();
				//합쳐도 사이클 형성 안되 경우만 합침 - 최소로 
				if(find(cur.s) != find(cur.e)) {
					union(cur.s, cur.e);
					useCost += cur.val;
					useEdge++;//하나씩 ++ 처리 -> N-1개되면 바로 탈출되겠지 
				}
			}
			
			//이제 최종 절약최대 비용은 전체 - 최소가중치합 
			
			System.out.println(sum - useCost);
		}
	}

}