[JAVA] BOJ(백준) - Watering the Fields - 10021

문제내용

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

10021번: Watering the Fields

Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000).

Each field i is described by a distinct point (xi, yi) in the 2D plane, with 0 <= xi, yi <= 1000. The cost of building a water pipe between two fields i and j is equal to the squared Euclidean distance between them:

(xi - xj)^2 + (yi - yj)^2

FJ would like to build a minimum-cost system of pipes so that all of his fields are linked together -- so that water in any field can follow a sequence of pipes to reach any other field.

Unfortunately, the contractor who is helping FJ install his irrigation system refuses to install any pipe unless its cost (squared Euclidean length) is at least C (1 <= C <= 1,000,000).

Please help FJ compute the minimum amount he will need pay to connect all his fields with a network of pipes.

입력

• Line 1: The integers N and C.
• Lines 2..1+N: Line i+1 contains the integers xi and yi.

출력

• Line 1: The minimum cost of a network of pipes connecting the fields, or -1 if no such network can be built.

---

문제 접근 방법

문제는 일단 다음과 같은 과정을 거쳤다.

모든 필드를 연결 시켜야한다? -> 그래프 활용? -> 최소비용으로 연결 시켜야한다? -> 굳이 사이클이 없어도 된다. -> MST(최소비용신장트리)를 이용해야겠군! -> 크루스칼 알고리즘이 어케 하더라..? ㅋㅋㅋㅋㅋㅋ

이과정을 거쳐서 풀게 됐다.

 

MST를 구현하는 알고리즘은 크루스칼과 프림알고리즘이 존재하는데 이전에 문제를 풀었을때도 프림보단 크루스칼을 주로 써서 풀었다(프림은 좀 어려움). 크루스칼 알고리즘을 이용하려면 Union-Find 알고리즘의 기본은 알아야한다. 그렇기 때문에 이문제는 MST 문제지만 Union-Find 알고리즘도 알아야하기 때문에 잘모르면 아래 링크 참고하자.

(크루스칼 활용 풀이 다른문제: https://record-developer.tistory.com/90 )

(Union-Find 기본 문제: https://record-developer.tistory.com/86 )

 

 

풀이 순서?

1.  크루스칼을 사용할것이기 때문에 정점과 간선이 필요.
2.  문제 입력값으로 주어진 위치는 정점이 아님 -> 행 하나가 진짜 정점임.
3. 즉, 문제에서 1행:(1,0) , 2행:(2,0) , 3행:(2,3) 으로 필드의 위치가 주어지면 필드의 위치는 정점이 아니고 필드 그자체(행하나)가 정점이된다.
4.  간선을 구해줘야됨. -> 문제에서 주어진 필드의 위치를 이용해서 구하면됨.
5.  정점과 간선의 가중치를 객체로 저장시키고 큐에 담아서 간선의 가중치로 정렬시켜줌.
6.  가중치가 C보다 작은것들은 무시.
7.  정점의 부모노드를 찾는다. -> 부모노드가 다르다 -> 그래프 끊겨있다 -> 이어준다(부모 노드를 하나로 일치시킨다).
8.  합칠때 마다 간선의 가중치를 정답 변수에 추가.
9.  스패닝트리 특징을 이용해 간선의 개수 = 정점의 개수 - 1 일때 탐색그만.
10.  최종적인 탐색후 간선의 개수 = 정점의 개수 - 1 이 아니면 -1을 출력. 그외에는 정답변수 출력.

 

---

코드

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

public class Main {
	static private int n,c,ans;
	static private int[] parents;
	static private PriorityQueue<Node> pq;
	static private class Node{
		int v1;
		int v2;
		int cost;
		public Node(int v1, int v2, int cost) {
			this.v1 = v1;
			this.v2 = v2;
			this.cost = cost;
		}
	}
	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());
		c = Integer.parseInt(st.nextToken());
		ans = 0;
		parents = new int[n];
		int[][] arr = new int[n][2];
		
		//arr -> 행: 정점 즉, 문제에서의 필드를 나타냄. 열: 정점(필드)의 위치
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			parents[i] = i;
		}
		
		//간선의 가중치 만들고 오름차순 정렬
		sortNode(arr);
		
		//스패닝트리는 간선개수가 정점개수-1이 어야됨. 당연히 mst도 마찬가지
		if(solution()!=n-1) System.out.println(-1);
		else System.out.println(ans);
		
		
		
	}

	public static void sortNode(int[][] arr) {
		pq = new PriorityQueue<Node>(new Comparator<Node>() {
			@Override
			public int compare(Node o1, Node o2) {
				int c1 = o1.cost;
				int c2 = o2.cost;
				if(c1>c2) return 1;
				else if(c1<c2) return -1;
				else return 0;
			}
		});
		
		//간선 구하고 정렬
		for(int i=0; i<n; i++) {
			int dis = 0;
			for(int j=i+1; j<n; j++) {
				dis = (arr[i][0]-arr[j][0])*(arr[i][0]-arr[j][0]) + (arr[i][1]-arr[j][1])*(arr[i][1]-arr[j][1]);
				Node node = new Node(i, j, dis);
				pq.add(node);
			}
		}
	}
	
	//크루스칼
	public static int solution() {
		int edge = 0;//간선 개수
		//간선의 가중치 순서대로 탐색
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			
			//정점
			int v1=cur.v1, v2=cur.v2;
			
			//가중치가 c보다 작으면 무시
			if(cur.cost<c) continue;
			
			//부모노드 찾기
			v1 = find(v1);
			v2 = find(v2);
			
			//부모노드가 다르면 -> 그래프가 끊겨있다. -> 이어줘야한다.
			if(v1 != v2) {
				//v2를 부모노드로 합치기
				parents[v1] = v2;
				//가중치 합
				ans+=cur.cost;
				//간선개수 추가
				edge++;
			}
			//mst가 그려졌으면 종료
			if(edge == n-1) break;
		}
		return edge;
	}
	
	public static int find(int v) {
		//부모노드가 자기자신일때.
		if(parents[v]==v) return v;
		
		//그게 아니면 재귀로 부모노드 찾을때까지 드감.
		return parents[v] = find(parents[v]);
	}
}

---

마치며

크루스칼 , 유니온-파인드 알고리즘은 이전에 공부하고 알고 있었는데 기억이 잘안나서 다시한번 공부하고 풀었다. 이전에 공부했던거라 수월하게 할수 있었다ㅎㅎ