BOJ_도시분할계획_1647

1. 과정

- 가장 적은 비용으로 모든 마을을 연결해야하니 MST문제이다.

- MST알고리즘은 대표적으로 Kruskal MST와 Prim MST가 있다.

- Kruskal MST는 가장 적은 비용부터 선택해 가며 Union-Find 기법을 사용하는 것이다. 그래서 처음에 비용순으로 정렬이 필요하다.

- Prim MST는 한 정점에서 시작해 인접한 모든 간선 중에 가장 적은 비용의 간선을 선택한다. 그래서 Priority Queue가 사용된다.

- 나는 Kruskal 알고리즘을 사용했다. 

 

 

 

2. 구현

언어 : JAVA

메모리 : 302,152 kb

시간 : 1,820 ms

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

public class BOJ_도시분할계획_1647 {
	static int N, M, answer;
	static int[] parent;
	static ArrayList<Pair> list;

	static class Pair {
		int n1, n2, w;

		public Pair(int n1, int n2, int w) {
			this.n1 = n1;
			this.n2 = n2;
			this.w = w;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		list = new ArrayList<>();
		for (int i = 0; i < M; ++i) {
			s = br.readLine().split(" ");
			list.add(new Pair(Integer.parseInt(s[0]), Integer.parseInt(s[1]), Integer.parseInt(s[2])));
		}
		// 비용순으로 정렬해 가장 적은 비용부터 연결
		Collections.sort(list, new Comparator<Pair>() {
			@Override
			public int compare(Pair o1, Pair o2) {
				return o1.w - o2.w;
			}
		});

		solve();
		System.out.println(answer);
	}

	private static void solve() {
		parent = new int[N + 1];
		for (int i = 1; i <= N; ++i)
			parent[i] = i;

		int last = 0;
		for (int i = 0; i < list.size(); ++i) {
			int n1 = list.get(i).n1;
			int n2 = list.get(i).n2;
			int w = list.get(i).w;
			if(union(n1, n2)) {
				answer += w;
				last = w;
			}
		}
		// 가장 마지막에 연결된 길 끊음(가장 큰 비용)
		answer -= last;
	}

	private static boolean union(int n1, int n2) {
		int find1 = find(n1);
		int find2 = find(n2);
		if (find1 != find2) {
			parent[find2] = find1;
			return true;
		}
		return false;
	}

	private static int find(int n2) {
		if (parent[n2] == n2)
			return n2;
		return parent[n2] = find(parent[n2]);
	}

}