[Gold4-JAVA] 백준 1647 - 도시 분할 계획

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

1647번: 도시 분할 계획

 

 

✅ 문제 요약

정점(집)과 간선(길)로 연결된 마을을 둘로 분리할 것인데 각 마을에서의 집들의 거리를 최소로 하고 싶다.

 

🛠️ 사용한 알고리즘

최소 스패닝 트리 - 크루스칼 알고리즘

 

🤔 문제 접근

처음 문제를 보고 어떻게 마을을 둘로 나눌 것인가 고민했다.

집 N개의 A마을, 집 M개의 B마을로 나누어 각각의 마을의 집들 사이의 최소 거리를 구해

완전 탐색으로 최소 비용일 경우를 구해야하나? 생각했지만 주어지는 데이터의 범위를 보고 이는 분명

시간초과가 날 것이라고 생각했다.

 

이 문제를 풀기 위해선 최소 스패닝 트리 - 크루스칼 알고리즘의 union-find 에 대해서 이해해야 했다.

초기 내 생각처럼 마을을 둘로 분리해 각 마을의 최소 비용들을 계산하는게 아닌, 

최소 스패닝 트리 알고리즘을 사용하여 전체 하나의 마을을 전부 연결하며 비용이 최소가 되는 것을

찾아야 했고 이 중, 최대 비용인 간선을 빼주면 (분리해주면) 최소 유지비용을 구할 수 있는 것이다.

 

최대 비용인 간선을 뺌으로써 분리된 A마을과 B마을이 있다고 한다면

A마을은 집(정점)이 존재하지만 연결된 최소 비용의 간선이 없기 때문에 유지비 0,

B마을은 이미 최소 스패닝 트리로 유지비용이 최소인 간선들로 이루어져 있기 때문에 가능한 풀이법이다.

 

최소 스패닝 트리의 프림 알고리즘 방법은 알고 있었지만 크루스칼 알고리즘은 처음 접하기 때문에

이해하는데 조금 어려움을 겪었던 문제다. 특히나 처음엔 union-find 를 하는 과정이 왜 필요한가 생각들었다.

union-find를 잘 설명해주는 글이 있으니 참고하면 좋을 것 같다.

 

[알고리즘] Kruskal Algorithm, Union Find (크루스칼 알고리즘, 유니온 파인드)

 

🚨CODE

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

class node implements Comparable<node>{
	int start;
	int end;
	int cost;
	public node(int start, int end, int cost) {
		this.start = start; 
		this.end = end;
		this.cost = cost;
	}
	
	public int compareTo(node n) {
		return this.cost - n.cost;
	}
}
public class Main {
	static int n,m;
	static int[] parent;
	static long result;
	static int max;
	static PriorityQueue<node> q = new PriorityQueue<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		parent = new int[n+1];
		for(int i = 1; i<=n; i++) {
			parent[i] = i;
		}
		
		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 c = Integer.parseInt(st.nextToken());
			
			q.add(new node(a, b, c));
		}

		while(!q.isEmpty()) {
			node poll = q.poll();
			if(!isParent(poll.start, poll.end)) {
				union(poll.start, poll.end);
				result += poll.cost;
				max = poll.cost;
			}
		}
		System.out.println(result - max);
	}
	public static int find(int x) {
		if(x == parent[x])
			return x;
		else
			return parent[x] = find(parent[x]);
	}
	public static boolean isParent(int x, int y) {
		int xp = find(x);
		int yp = find(y);
		if(xp != yp)
			return false;
		else
			return true;
	}
	public static void union(int x, int y) {
		int xp = find(x);
		int yp = find(y);
		parent[yp] = xp;
	}
}