백준 - 도시 분할 계획(1647) - 최소신장트리 - Java

1. 문제

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

2-1. 크루스칼 풀이

두 마을로 나누고, 두 마을 안에서도 최소 경로 합을 보장할려면
모든 노드를 연결하는 최소신장트리 - 가장 긴 경로 값을 하게 되면 도시도 분할되고 각 마을 경로의 합 최소를 보장한다.

3-1. 크루스칼 코드

import java.util.*;

public class Main {
	
	public static class Node implements Comparable<Node>{
		
		int distance;
		int nowNode;
		int nextNode;
		
		public Node(int d, int a, int b) {
			distance = d;
			nowNode = a;
			nextNode = b;
		}

		@Override
		public int compareTo(Node other) {
			
			return (this.distance - other.distance);
		}
            
	}
	
	public static int parent[];

	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		int M = input.nextInt();
		
		parent = new int[N+1];
		for(int p = 0; p < parent.length; p++)
			parent[p] = p;
		
		ArrayList<Node> City = new ArrayList<Node>();
		
		for(int m = 0; m < M; m++) {
			
			int a = input.nextInt();
			int b = input.nextInt();
			int c = input.nextInt();
			
			City.add(new Node(c, a, b));
		}
		
		Collections.sort(City);
		
		int sum = 0;
		int long_distance = 0;
		
		for(int i = 0; i < City.size(); i++) {
			
			int distance = City.get(i).distance;
			int nowNode = City.get(i).nowNode;
			int nextNode = City.get(i).nextNode;
			
			if(find_parent(nowNode) != find_parent(nextNode)) {
				
				union_parent(nowNode, nextNode);
				sum += distance;
				long_distance = distance;
			}
		}
		
		System.out.println(sum - long_distance);

	}
	
	public static void union_parent(int a, int b) {
		
		a = find_parent(a);
		b = find_parent(b);
		
		if(a < b)
			parent[b] = a;
		
		else
			parent[a] = b;
	}
	
	public static int find_parent(int x) {
		
		if(parent[x] == x)
			return x;
		
		else
			return parent[x] = find_parent(parent[x]);
	}

}

2-2. 프림 풀이

2-3. 프림 코드

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

public class Main{
	
	public static class Node implements Comparable<Node>{
		
		int distance;
		int nowNode;
		
		public Node(int d, int a) {
			distance = d;
			nowNode = a;
		}

		@Override
		public int compareTo(Node other) {
			return (this.distance - other.distance);
		}
            
	}

	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 M = Integer.parseInt(st.nextToken());
		
		//ArrayList<Node> City = new ArrayList<Node>();
		boolean[] visit = new boolean[N+1];
		ArrayList<ArrayList<Node>> City = new ArrayList<>();
		for(int i = 0; i <= N; i++) {
			City.add(new ArrayList<>());
		}
		
		for(int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			City.get(a).add(new Node(c, b));
			City.get(b).add(new Node(c, a));
		}
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(0, 1)); // 시작 cost = 0, 시작노드 = 1
		
		int sum = 0;
		int long_distance = 0;
		
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			
			if(visit[node.nowNode]) continue;
			
			visit[node.nowNode] = true;
			sum += node.distance;
			long_distance = Math.max(long_distance, node.distance);
			
			for(Node n : City.get(node.nowNode)) {
				if(!visit[n.nowNode]) {
					pq.add(new Node(n.distance, n.nowNode));
				}
			}
		}
		
		System.out.println(sum - long_distance);

	}

}