도시 분할 계획

문제

아이디어

크루스칼 알고리즘 사용하기

최소 신장 트리는 그래프 내의 모든 정점을 포함하고, 트리
사용된 간선들의 가중치 합이 최소인 트리를 의미한다.

즉 노드가 7개가 있으면
간선 6개를 사용해서 모든 노드가 연결되고 이 중 최소 비용의 간선을 찾는 것이다.

이 문제에서 이 아이디어를 적용할 수 있다.

조건중 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.
, 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다 을 생각해봐야한다.

또한 길의 유지비의 합을 최소로 한다고 했으므로 최소 신장 트리를 구하면 된다.

여기서 2개의 마을 분리한다고 했으므로 최소 신장 트리 중 가장 큰 비용의 간선을 제거하면 결국 2개의 마을이 분리되고 그 마을은 서로 연결 되어 있을 것이다.

코드

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static Edge[] EdgeList;
	static int[] parents;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("./input.txt"));
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		EdgeList = new Edge[M];
		parents = new int[N + 1];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			
			Edge edge = new Edge(from, to, dist);
			EdgeList[i] = edge;
		}
		
		Arrays.sort(EdgeList);
		
		make();
		
		int cnt = 0;
		int ans = 0;
		int max_num = 0;
		
		for (Edge edge : EdgeList) {
			int from = edge.from;
			int to = edge.to;
			int dist = edge.dist;
			
			if (!union(from, to)) continue;
			ans += dist;
			
			max_num = Math.max(max_num, dist);
		}
		
		System.out.println(ans - max_num);
	}
	
	static void make() {
		for (int i = 1; i <= N; i++) parents[i] = i;
	}
	
	static int find(int a) {
		if (parents[a] == a) return a;
		return parents[a] = find(parents[a]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if (aRoot == bRoot) return false;
		parents[aRoot] = parents[bRoot];
		return true;
		
	}
	
}

class Edge implements Comparable<Edge>{
	int from, to, dist;

	public Edge(int from, int to, int dist) {
		this.from = from;
		this.to = to;
		this.dist = dist;
	}

	@Override
	public int compareTo(Edge o) {
		return this.dist - o.dist;
	}

	@Override
	public String toString() {
		return "Edge [from=" + from + ", to=" + to + ", dist=" + dist + "]";
	}
	
	
}

크루스칼은 2가지만 기억하면 된다. 유니온 파인드와 그리디이다.
일단 모든 간선 중 최소 간선를 선택하고 서로 유니온 시켜주는 것이다.
만약 유니온이 될 수 없을 때, 즉 사이클이 발생하는 노드는 제외하고 최소 간선을 찾으면 된다.