백준 10021 : Watering the Fields (JAVA, MST)

최소 신장 트리 (MST, Minimum Spanning Tree)

 

Spanning Tree

 - 그래프 내의 모든 정점을 포함하는 트리

 - 그래프의 최소 연결 부분 그래프

 - 모든 정점들이 연결되어 있어야 하고, 사이클을 포함해서는 안됨

 - 그래프에 있는 n개의 정점을  n-1 개의 간선으로 연결

 

MST의 특징

 - 간선의 가중치의 합이 최소

 - n개의 정점을 가지고 그래프에 대해 n-1 개의 간선만을 사용

 - 사이클을 포함해서는 안됨

 

---

문제

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

 

풀이

처음에는  DFS + 백트래킹으로 풀었다가 시간 초과

이 문제는 MST 알고리즘으로 풀어야한다

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

class Main {

	static String[] input;
	static StringBuilder sb = new StringBuilder();
	static int N, C;
	static int[] parent;

	// 유니온 파인드
	// 부모(root) 노드를 찾는 과정
	static int find(int n) {
		if (n == parent[n])
			return n;
		return parent[n] = find(parent[n]);
	}

	// 연결된 두 노드의 부모 노드를 찾고, 하나의 부모 노드로 동기화 시켜준다
	static void union(int x, int y) {
		x = find(x);
		y = find(y);

		// 다른 부모 노드 값이 나온다면, 인덱스 값이 더 작은 노드를 부모 노드로 정한다
		if (x < y)
			parent[y] = x;
		else
			parent[x] = y;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		C = Integer.parseInt(input[1]);

		Node[] node = new Node[N];
		for (int i = 0; i < N; i++) {
			input = br.readLine().split(" ");

			// Node( x좌표, y좌표, 0) 으로 생각
			node[i] = new Node(Integer.parseInt(input[0]), Integer.parseInt(input[1]), 0);
		}

		// 비용(cost)가 적은
		PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.cost - n2.cost);

		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				int cost = (int) Math.pow(node[i].x - node[j].x, 2) + (int) Math.pow(node[i].y - node[j].y, 2);
				// 노드간 비용이 최소 비용을 넘어야만 (관계를 사용할 수 있기 때문에) 우선순위 큐에 넣는다.
				if (C <= cost) {
					// Node ( i번호 노드, j번호 노드, 비용)
					pq.add(new Node(i, j, cost));
				}
			}
		}

		// 노드들의 부모 노드를 자기 자신으로 초기화
		parent = new int[N];
		for (int i = 0; i < N; i++)
			parent[i] = i;

		int result = 0;
		int count = 0; // 모든 정점을 방문했는지 확인하기 위한 변수

		// 우선순위 큐는 가장 최소 비용을 가진 노드 관계를 우선적으로 뽑는다
		while (!pq.isEmpty()) {
			Node n = pq.poll(); // x번 노드, y번 노드, 비용
			if (find(n.x) == find(n.y)) // 노드 관계가 확인된 것이라면 continue
				continue;

			union(n.x, n.y); // union 합친다
			count += 1; // 1개의 노드 관계를 카운트
			result += n.cost;
		}

		// 노드 개수가 N개라면 관계는 N-1개이다. 위에서 중복되지않고 모든 노드를 차례로 관계를 확인했다면 count == N-1
		System.out.println(count < N - 1 ? -1 : result);
		br.close();
	}

}

class Node {
	int x, y, cost;

	Node(int x, int y, int cost) {
		this.x = x;
		this.y = y;
		this.cost = cost;
	}
}

 

 

---

참고 사이트

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog