[BaekJoon] 1647 도시 분할 계획 (Java)

1.  문제 링크

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

2.  문제

요약

• 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있고, 길은 어느 방향으로든지 다닐 수 있는 편리한 길입니다.
• 각 길마다 길을 유지하는데 드는 유지비가 있습니다.
• 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있고, 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 합니다.
• 마을에는 집이 하나 이상 있어야 합니다.
• 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있습니다.
• 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 최소 합을 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100,000보다 작거나 같은 정수인 집의 개수 N과 1보다 크거나 같고 1,000,000보다 작거나 같은 정수인 길의 개수 M이 주어지고 두 번째 줄부터 M개의 줄에는 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 1보다 작거나 같고 1,000보다 작거나 같은 C라는 뜻입니다.
• 출력: 첫 번째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[][] edges;
	static int[] parents;
	static HashMap<Integer, ArrayList<Integer>> map;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		edges = new int[M][3];
		parents = new int[N + 1];
		for(int house = 1; house <= N; house++) parents[house] = house;
		for(int edge = 0; edge < M; edge++) {
			int n1 = scanner.nextInt(), n2 = scanner.nextInt(), weight = scanner.nextInt();
			int min = Math.min(n1, n2), max = Math.max(n1, n2);
			edges[edge][0] = min;
			edges[edge][1] = max;
			edges[edge][2] = weight;
		}
	}
	
	static void solution() {
		Arrays.sort(edges, new Comparator<int[]>() {
			public int compare(int[] e1, int[] e2) {
				if(e1[2] != e2[2]) return e1[2] - e2[2];
				else {
					if(e1[0] != e2[0]) return e1[0] - e2[0];
					else return e1[1] - e2[1];
				}
			}
		});
		int result = kruskal();
		System.out.println(result);
	}
	
	static int kruskal() {
		ArrayList<int[]> mst = new ArrayList<>();
		int totalWeight = 0;
		for(int[] edge : edges) {
			if(mst.size() == N - 1) break;
			if(mst.size() >= N - 2) {
				for(int house = 1; house <= N; house++) findParents(house);
				int count = 0;
				HashSet<Integer> set = new HashSet<>();
				for(int house = 1; house <= N; house++) {
					if(set.add(parents[house])) count++;
				}
				if(count == 2) break;
			}
			if(!isSameParents(edge[0], edge[1])) {
				union(edge[0], edge[1]);
				mst.add(edge);
			}
		}
		for(int index = 0; index < mst.size(); index++) totalWeight += mst.get(index)[2];
		return totalWeight;
	}
	
	static int findParents(int house) {
		if(house == parents[house]) return house;
		return parents[house] = findParents(parents[house]);
	}
	
	static void union(int house1, int house2) {
		int parent1 = findParents(house1), parent2 = findParents(house2);
		if(parent1 != parent2) {
			if(parent1 < parent2) parents[parent2] = parent1;
			else parents[parent1] = parent2;
		}
	}
	
	static boolean isSameParents(int house1, int house2) {
		int parent1 = findParents(house1), parent2 = findParents(house2);
		if(parent1 == parent2) return true;
		return false;
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}