백준 1647 도시 분할 계획 (Java)

1. 문제 링크

1647번: 도시 분할 계획

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. MST 문제로 크루스칼 알고리즘을 이용했다.

2. 노드를 가중치 기준으로 정렬한다.

3. 두 집이 연결되어 있지 않다면 연결한다.

    4-1. 1번 코드는 전체를 다 연결하고 최대 연결 수까지의 값을 더한 것이다.

    4-2. 2번 코드는 전체를 다 연결하고 최댓값 하나만 빼준 것이다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
	static class Node implements Comparable<Node>{
		int A, B, C;
		public Node(int a, int b, int c) {
			super();
			A = a;
			B = b;
			C = c;
		}
		@Override
		public int compareTo(Node o) {
			return this.C - o.C;
		}
	}

	static ArrayList<Node> list;
	static int[] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int M = Integer.parseInt(split[1]);
		list = new ArrayList<>();
		for(int i=0;i<M;i++) {
			split = br.readLine().split(" ");
			int a = Integer.parseInt(split[0]);
			int b = Integer.parseInt(split[1]);
			int c = Integer.parseInt(split[2]);
			list.add(new Node(a,b,c));
		}

		parent = new int[N+1];
		for(int i=1;i<N+1;i++) {
			parent[i] = i;
		}
		
		Collections.sort(list);
		
		int[] cost = new int[N-1];
		int cnt = 0;
		for(Node now : list) {
			if(find(now.A)!=find(now.B)) {
				cost[cnt] = now.C;
				union(now.A, now.B);
				cnt++;
			}
		}
		
		int result = 0;
		for(int i=0;i<N-2;i++) { 
			result += cost[i];
		}
		
		System.out.println(result);
	}
	
	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a!=b) {
			parent[b] = a;
		}
	}
	
	private static int find(int a) {
		if(parent[a] == a) {
			return a;
		}
		else {
			return parent[a] = find(parent[a]);
		}
	}
}