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

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

1647번: 도시 분할 계획

생각

마을을 두개로 분리해야하고 분리된 마을들은 내부에서 서로 모두 연결되어있어야 합니다. 또한 분리된 마을들은 최소의 비용으로 서로 모두 연결되어있어야 합니다. 즉, 그래프에서 최소 비용을 찾는 문제로 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리인 MST(최소 신장 트리)를 구성해야 합니다.

 

이를 만족하기 위해서 아래의 작업을 수행해줍니다.

 

1. 모든 마을들을 최소 스패닝 트리로 만든다.

2. 간선리스트를 정렬하여 가중치가 가장 낮은 간선부터 하나씩 선택하는 크루스칼 알고리즘을 사용하여 구현.

3. 가장 비용이 높은 길을 끊어버린다 == 총 연결 비용에서 마지막 연결 비용을 빼줍니다 -> 마을이 두개의 집합으로 분리된다.

 

 

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_1647_도시분할 {
	static int N,M;
	static List<Node> adjList;
	static int parents[];
	
	static class Node implements Comparable<Node>{
		int from,to,cost;

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

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.cost, o.cost); // 비용 적은순으로
		}

		@Override
		public String toString() {
			return "Node [from=" + from + ", to=" + to + ", cost=" + cost + "]";
		}
		
	}
	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());
		adjList = new ArrayList<Node>();
		
		
		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 cost = Integer.parseInt(st.nextToken());
			adjList.add(new Node(from, to, cost));
		}
		
		parents = new int[N+1];
		
		Collections.sort(adjList);
		makeParents();
		int ans = 0;
		int max = 0;
		for (int i = 0; i < adjList.size(); i++) {
			Node now = adjList.get(i);
			if(find(now.from) != find(now.to)) {
				
				union(now.from, now.to);
				ans += now.cost;
				max = now.cost; // 마지막 갱신이 최대비용
			}
			
			
		}
		System.out.println(ans-max);

	}
	
	private static void makeParents() {
		for (int i = 1; i <= N; i++) {
			parents[i] = i;
		}
	}
	
	//v의 루트 노드 찾기
	private static int find(int v) {
		if(v == parents[v]) {
			return v;
		}
		return parents[v] = find(parents[v]);
	}
	
	//a집합에 b를 흡수
	private static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot == bRoot) return false;
		parents[bRoot] = aRoot;
		return true;
	}
	

}