[SWEA] 하나로

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

MST 문제로 kruskal 알고리즘을 사용해 문제를 해결한다.

JAVA Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {
	static int N; 
	static int[] parent; 
	static boolean[] visit;
	static ArrayList<Edge> mst;
	static PriorityQueue<Edge> pq;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T;tc++) {
			N = sc.nextInt();
			int[] x = new int[N];
			int[] y = new int[N];
			visit = new boolean[N + 1];
			parent = new int[N + 1];
			pq = new PriorityQueue<>(new EdgeComparator());
			mst = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				x[i] = sc.nextInt();
			}
			for (int i = 0; i < N; i++) {
				y[i] = sc.nextInt();
			}
			double E = sc.nextDouble();
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if ( i == j ) {
						continue;
					}
					long value = (long)(Math.pow(x[i]-x[j],2)+(long)Math.pow(y[i]-y[j],2));
					pq.add(new Edge(i,j,value));
				}
			}
			kruskal();
			double sum = 0;
			
			for(int i=0; i<mst.size(); i++) {
				sum += mst.get(i).value * E;
			}
			System.out.printf("#%d %.0f\n",tc,sum);
		}
	}
	
	static void kruskal() {
		for(int i=1; i<N; i++) { 
			parent[i] = i;
		}
		int len = pq.size();
		for(int i=0; i<len; i++) {
			Edge edge = pq.poll();
			if(find(edge.start) == find(edge.end)) {
				continue;
			}
			union(edge.start, edge.end); 
			mst.add(edge);
		}
		
	}
	
	static int find(int n) { 
		if (parent[n] == n) {
			return n;
		}
		parent[n] = find(parent[n]); 
		return parent[n];
	}
	
	static void union(int n1, int n2) { 
		int p1 = find(n1);
		int p2 = find(n2);

		if (p1 != p2) { 
			parent[p1] = p2;
		}
	}

	static class EdgeComparator implements Comparator<Edge> {
		@Override
		public int compare(Edge o1, Edge o2) {
			return o1.value > o2.value ? 1 : -1;
		}

	}
	
	static class Edge { 
		int start, end;
		long value;

		Edge(int s, int e, long v) {
			start = s;
			end = e;
			value = v;
		}
		@Override
		public String toString() {
			return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
		}
	}
}