6 min to read

java 크루스칼알고리즘 백준 도시건설 21924

백준-크루스칼-알고리즘-도시건설

Featured image

크루스칼 알고리즘

크루스칼 알고리즘의 개념을 구글링 해서 꼭 알고 풀자

저번 하나로 swea 문제보다 조금 더 쉬운

크루스칼의 기본 문제라고 할 수 있는 도시건설을 풀어보았다.

BOJ 21924 도시건설

문제출처 - https://www.acmicpc.net/problem/21924

문제

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.

채완이는 공사하는 데 드는 비용을 아끼려고 한다.

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.

문제 설명

이미 문제에서 “비용을 아끼려한다”

“최소한의 도로를 만들려고한다.”

최단거리 알고리즘을 사용하라고 다 말해줬다.

[입력]

첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$

$(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다.

두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 건물 사이 도로를 만들 때 드는 비용 $c (1 \le c \le 10^6)$가 주어진다. 같은 쌍의 건물을 연결하는 두 도로는 주어지지 않는다.

[출력]

예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 도시건설 {
	static int N, M;
	static long result, original;
	static int parent[];
	static ArrayList<Node> arr[];

	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()); // 도로의 개수
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		original = 0;
		result = 0;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			// 1,2,15 1->2로 15비용
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			long weight = Integer.parseInt(st.nextToken());
			pq.add(new Node(start, end, weight));
			original += weight;
		}
		parent = new int[N + 1];
		for (int i = 0; i <= N; i++) {
			parent[i] = i;
		}
		int count = 0;
		while (!pq.isEmpty()) {
			if (count == N - 1) {
				break;
			}
			Node node = pq.poll();
			// 연결되어있지 않다면 연결
			boolean flag = unionSet(node.start, node.end);
			if(flag) {
				count++;
				result += node.weight;
			}
		}
		int check = parent[1];
		for(int i = 1; i<parent.length;i++) {
			if(findSet(parent[i])!=check) {
				System.out.println("-1");
				return;
			}
		}
		System.out.println(original-result);
	}

	private static boolean unionSet(int start, int end) {
		int startX = findSet(start);
		int endY = findSet(end);
		if(startX!=endY) {
			if(startX>endY) {
				parent[startX] = endY;
			}else {
				parent[endY]=startX;
			}
			return true;
		}else {
			return false;
		}
	}

	private static int findSet(int start) {
		if (parent[start] == start) {
			return start;
		}
		return findSet(parent[start]);
	}

	static class Node implements Comparable<Node> {
		int start;
		int end;
		long weight;

		Node(int start, int end, long weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			if (o.weight > this.weight) {
				return -1;
			}
			return 1;
		}
	}
}

모든 도시들을 연결하기 위해서 각자 자신의 도시 번호를 붙인뒤

		parent = new int[N + 1];
		for (int i = 0; i <= N; i++) {
			parent[i] = i;
		}

이동을 할때마다 모든 도시들이 이미 연결이 되어있는지

연결이 필요한지 findSet과 UnionSet을 이용해서 확인합니다.

아래의 두 함수가 간단하게 findSet과 UnionSet을 구현한것입니다.

	private static boolean unionSet(int start, int end) {
		int startX = findSet(start);
		int endY = findSet(end);
		if(startX!=endY) {
			if(startX>endY) {
				parent[startX] = endY;
			}else {
				parent[endY]=startX;
			}
			return true;
		}else {
			return false;
		}
	}
	private static int findSet(int start) {
		if (parent[start] == start) {
			return start;
		}
		return findSet(parent[start]);
	}