도시분할계획 [백준 1647][JAVA][골드 4][프림][크루스칼][MST]

 

[광고 누르면 오늘의 행운 상승!!]

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

1647번: 도시 분할 계획

최소스패닝트리와 매우 유사한 문제이다.

최단이동경로를 프림과 크루스칼을 이용하여 구한 후 가장 긴 간선을 제거한다.

<<프림코드>>

package Study5;

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


public class 도시분할계획 {
	static class Edge implements Comparable<Edge>{
		int node, dis;
		public Edge(int node, int dis) {
			this.node =  node;
			this.dis = dis;
		}
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.dis, o.dis);
		}
	}
	static int N,M,DISTANCE,cnt;
	static ArrayList<ArrayList<Edge>> graph;
	static PriorityQueue<Edge> pq;
	static boolean visit[];
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.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());
		
		graph = new ArrayList<>();
		pq = new PriorityQueue<>();
		visit = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<>());
		}
		int temp = Integer.MAX_VALUE;
		int start = 0;
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken())-1;
			int B = Integer.parseInt(st.nextToken())-1;
			int dis = Integer.parseInt(st.nextToken());
			
			graph.get(A).add(new Edge(B,dis));
			graph.get(B).add(new Edge(A,dis));
			
			if(temp > dis) {
				temp = dis;
				start = A;
			}
		}
		pq.add(new Edge(start,0));
		
		int max = Integer.MIN_VALUE;
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			if(visit[edge.node]) continue;
			visit[edge.node] = true;
			
			max = (max < edge.dis)? edge.dis : max; 
			DISTANCE += edge.dis;
			for (Edge next : graph.get(edge.node)) {
				if(!visit[next.node]) pq.add(next);
			}
			
			if(++cnt == N) break;
		}
		
		
		System.out.println(DISTANCE - max);
	}
}

 

<<크루스칼 코드>>

package Study5;

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

public class 도시분할계획크루스칼 {
	
	public static class Edge implements Comparable<Edge> {
		int a;
		int b;
		int w;
		public Edge(int a, int b, int w) {
			this.a = a;
			this.b = b;
			this.w = w;
		}
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(w, o.w);
		}
	}
	
	public static int N, M, ans;
	public static int[] p;
	
	public static void union(int x, int y) {
		p[findSet(y)] = findSet(x);
	}
	
	public static int findSet(int x) {
		if (p[x] == x) return x;
		return p[x] = findSet(p[x]);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		p = new int[N+1];
		for (int i = 1; i <= N; i++) {
			p[i] = i;
		}
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			pq.add(new Edge(a, b, w));
		}
		
		
		int cnt = 0;
		while(!pq.isEmpty()) {
			Edge cur = pq.poll();
			if(findSet(cur.a) == findSet(cur.b))
				continue;
			
			ans+=cur.w;
			if (++cnt == N-2) break;
			union(cur.a, cur.b);
		}
		
		System.out.println(ans);
	}
}