백준 1647 : 도시 분할 계획

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

1647번: 도시 분할 계획

[ 문제풀이 ]

기본적으로 MST를 활용해야 하는 문제이다.

다만, N이 최대 100,000이기때문에 마을을 두 그룹으로 분할할 수 있는 모든 경우에 MST를 적용한다면 당연히 TLE가 발생할 것이다.

주어진 예제로 정답 8인 경로를 만들어보면 (N-1)개의 정점까지만 MST를 구성해주면 된다는 것을 알 수 있다.

왜냐하면 (N-1)개의 정점(마을 1)까지의 MST를 구했다는 것은 주어진 간선으로 최소 유지비를 구하는 것이기 때문에 남은 한 개의 집은 아무런 집과 연결되지 않은 마을 2로 생각하면 되기 때문이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static class Edge implements Comparable<Edge> {
		int from, to, cost;

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

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}
	
	static int N, M;
	static int[] parent;
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			parent = new int[N + 1];
			for (int i = 0; i <= N; ++i) parent[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 C = Integer.parseInt(st.nextToken());
				pq.offer(new Edge(A, B, C));
			}
			
			//MST를 (N-1)개의 정점까지 구성하면 됨
			int connect = 1, sum = 0;
			while (connect != N - 1 && !pq.isEmpty()) {
				Edge e = pq.poll();
				if (union(e.from, e.to)) {
					sum += e.cost;
					connect++;
				}
			}
			bw.write(sum + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static int getParent(int v) {
		return parent[v] == v ? v : (parent[v] = getParent(parent[v]));
	}
	
	public static boolean union(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		
		if (a == b) return false;
		parent[b] = a;
		return true;
	}
}