그래프 이론 - 3. 어두운 길

문제

한 마을은 N개의 집과 M개의 도로로 구성되어 있다.
각 집은 0번부터 N-1번까지의 번호로 구분된다. 모든 도로에는 가로등이 구비되어 있는데,
특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일하다.
정부에서 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여
가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 한다.
결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 한다.
마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하라.

예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 하면, 하루 동안 이 가로등을 켜기 위한 비용은 7이다.

입력 조건

• 첫째 줄에 집의 수 N (1 <= N <= 200,000)과 도로의 수 M (N-1 <= M <= 200,000)이 주어진다.
• 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X, Y, Z가 주어지며, 공백으로 구분한다.
  (0 <= X, Y < N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미이다.
  단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이 합은 2 ^ 31 보다 작다.

출력 조건

• 첫째 줄에 일부 가로등을 비활성화 하여 절약할 수 있는 최대 금액을 출력하라.

입력 예시
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11

출력 예시
51

구현코드

import java.io.*;
import java.util.*;

class Edge implements Comparable<Edge>{
	private int node1;
	private int node2;
	private int distance;
	
	public Edge(int node1, int node2, int distance){
		this.node1 = node1;
		this.node2 = node2;
		this.distance = distance;
	}
	public int getNode1(){
		return this.node1;
	}
	public int getNode2(){
		return this.node2;
	}
	public int getDistance(){
		return this.distance;
	}
	
	@Override
	public int compareTo(Edge other){
		return Integer.compare(this.distance, other.distance);
	}
}
public class Main{
	
	public static int[] parent;
	public static int findParent(int a){
		if(a == parent[a]) return a;
		else return parent[a] = findParent(parent[a]);
	}
	public static void unionParent(int a, int b){
		a = findParent(a);
		b = findParent(b);
		if(a < b) parent[b] = a;
		else parent[a] = b;
	}
	
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		ArrayList<Edge>graph = new ArrayList<>();
		parent = new int[n];
		// 부모노드를 자기자신으로 초기화
		for(int i = 0 ; i < n ; i++){
			parent[i] = i;
		}
		// 모든 비용과 최소비용을 할당.
		int sum = 0;
		int min = 0;
		for(int i = 0; i < e; i++){
			st = new StringTokenizer(br.readLine());
			int node1 = Integer.parseInt(st.nextToken());
			int node2 = Integer.parseInt(st.nextToken());
			int distance = Integer.parseInt(st.nextToken());
			sum += distance;
			graph.add(new Edge(node1, node2, distance));
		}
		// 입력받은 그래프를 오름차순으로 정렬
		Collections.sort(graph);
		for(int i = 0 ; i < e; i++){
			Edge now = graph.get(i);
			if(findParent(now.getNode1()) != findParent(now.getNode2())){
				unionParent(now.getNode1(), now.getNode2());
				min += now.getDistance();
			}
		}
		System.out.println(sum - min);
	}
}

코드해석

이 문제는 최소신장 트리를 만드는 크루스칼 알고리즘을 이용하여 풀면된다. 크루스칼 알고리즘만 익히고있다면 풀수있는 문제이다.