[SWEA 1251] 하나로(JAVA/C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

SW Expert Academy

 

 

작년 A형 시험에 MST문제가 나와서 된통 당하고, 풀어봤던 문제이다..

자바로 다시 풀어볼 기회가 생겨서 풀어봤다.

크루스칼 알고리즘으로 풀었는데, 프림 알고리즘도 더 공부해서 써봐야겠다.

long 타입으로 지정해 줘야 하는 변수를 잘 확인하자!

 

[JAVA]

package day3;

import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Scanner;

class Connect implements Comparable<Connect>{
	long d;
	int from;
	int to;
	public Connect(long d, int from, int to) {
		super();
		this.d = d;
		this.from = from;
		this.to = to;
	}
	@Override
	public int compareTo(Connect o) {
		return Long.compare(this.d, o.d);
	}
	
	
}
public class Solution_d4_1251_하나로 {

	static int N;
	static long total;
	static int[] parents;
	static double E;
	static long[] X;
	static long[] Y;
	static long[][] dist;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(new InputStreamReader(System.in));
		int T=sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N=sc.nextInt();
			X=new long[N];
			Y=new long[N];
			dist=new long[N][N];
			parents=new int[N];
			for(int i=0; i<N; i++) X[i]=sc.nextLong();
			for(int i=0; i<N; i++) Y[i]=sc.nextLong();
			E=sc.nextDouble();
			//입력끝
			
			for(int i=0; i<N; i++) parents[i]=i;
			PriorityQueue<Connect> pq=new PriorityQueue<Connect>();
			for(int i=0; i<N; i++) {
				for(int j=i+1; j<N; j++) {
					if(i==j)continue;
					long L=(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
					dist[i][j]=L;
					dist[j][i]=L;
					pq.offer(new Connect(L,i,j));
				}
			}
			int cnt=0;
			total=0;
			while(!pq.isEmpty()) {
				if(cnt==N-1) break;
				Connect c=pq.poll();
				if(isUnion(c.from,c.to)) continue;
				cnt++;
				total+=c.d;
				
			}
			System.out.println("#"+tc+" "+Math.round(E*total));
		}
	}

	private static boolean isUnion(int from, int to) {
		int pf=find(from);
		int pt=find(to);
		if(pf==pt) return true;
		parents[(int) pf]=pt;
		return false;
	}

	private static int find(int x) {
		if(parents[x]==x) return x;
		else return parents[x]=find(parents[x]);
	}

}

 

 

[C++]

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int N;
int parent[1000];
double e;
long long dist[1000][1000];


long long Find(long long i) {
	if (parent[i] == i) return i;
	else return parent[i] = Find(parent[i]);
}
bool Union(long long i, long long j) {
	long long pi = Find(i);
	long long pj = Find(j);
	if (pi == pj) return 1;

	parent[pi] = pj;
	return 0;
}
int main() {
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		priority_queue<pair<long long, pair<long long, long long> > > pq;
		memset(dist, 0, sizeof(dist));
		memset(parent, 0, sizeof(dist));
		long long X[1000];
		long long Y[1000];
		cin >> N;
		for (int i = 0; i < N; i++)
			cin >> X[i];		
		for (int i = 0; i < N; i++)
			cin >> Y[i];
		cin >> e;
		//입력끝
		for (long long i = 0; i < N; i++)
			parent[i] = i;//맨처음 부모값 자신으로 초기화
		for (long long i = 0; i < N; i++) {
			for (long long j = i + 1; j < N; j++) {
				//거리 구하기
				dist[i][j] = ((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]));
				dist[j][i] = dist[i][j];
				pq.push({ -dist[i][j],{i,j} });
			}
		}
		int cnt = 0;
		double total = 0;
		while (!pq.empty()) {
			if (cnt == N - 1) break;
			long long d = -pq.top().first;
			long long first = pq.top().second.first;
			long long second = pq.top().second.second;
			pq.pop();
			bool f = Union(first, second);
			if (f == 1) {
				continue;
			}
			cnt++;
			total += d;
		}
		printf("#%d %0.lf\n", tc, e * total);
	}

	return 0;
}