[白俊]4386号:星座の作成(Java)

https://www.acmicpc.net/problem/4386
質問する
道現は宇宙の神である.今、道現は横に7つの星をつなぎ、星座を構成します.星座の条件は以下の通りです.

星座をつくる線は、2つの異なる星を一直線に結ぶ形.

すべての星は星座の上の線で直接または間接的に結ばれなければならない.

星は2 D平面上に配置されます.1本の線を接続するたびに2つの星との距離が等しいと言ったら、星座を作成する最小コストを求めます.
入力
最初の行は星の個数nを与えた.(1 ≤ n ≤ 100)
2行目からn行目まで、各星のx,y座標は実数形式で与えられ、最大小数点から2位まで与えられる.座標は1000を超えない量の実数です.

3
1.0 1.0
2.0 2.0
2.0 4.0

しゅつりょく
1行目に正解を出力します.絶対/相対誤差は10-2の間で許容される.

3.41

に答える
グラフ問題でMSTアルゴリズムを用いた問題.問題で説明されている星座条件がMSTの条件だからです.Kruskal/PRimはどの方向に解いても構わないが,ここではPrimアルゴリズムを用いた.
この問題では,図形の頂点に2次元座標が与えられるため,幹線を求める費用(長さ)は単独で計算する必要がある.ピタゴラスの公式を適用して2点間の距離を求めればよい.

// 거리 계산
public static double calDist(Star a, Star b) {
	return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
}

Math.sqrt():平方根を求める方法

Math.pow():平方を求める方法

最後に小数点の2番目に印刷します!

System.out.printf("%.2f", result);

完全なコード

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

// 별의 위치 저장
class Star {
	double x;
	double y;

	Star(double x, double y) {
		this.x = x;
		this.y = y;
	}
}

// 인접한 별과 간선의 비용(거리) 저장
class StarDist implements Comparable<StarDist> {
	int star;
	double dist;

	StarDist(int star, double dist) {
		this.star = star;
		this.dist = dist;
	}

	@Override //우선순위 큐를 이용하기 위해
	public int compareTo(StarDist d) {
		return (int) (this.dist - d.dist);
	}
}

public class BJ_4386 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Star[] stars = new Star[n]; // 별의 위치
        boolean[] visited = new boolean[n]; // 방문 여부
		double[] distance = new double[n]; // 시작 정점에서부터 각 정점 사이의 거리
        // 별과 간선의 정보를 담는 그래프
		ArrayList<ArrayList<StarDist>> graph = new ArrayList<>(); 
		
		for (int i = 0; i < n; i++) {
			distance[i] = Double.MAX_VALUE; // 거리 초기화
			graph.add(new ArrayList<>()); // 그래프 구현
		}

		// 입력
		for (int i = 0; i < n; i++) {
			double x = sc.nextDouble();
			double y = sc.nextDouble();
			stars[i] = new Star(x, y);
			for (int j = 0; j < i; j++) {
				double dist = calDist(stars[i], stars[j]);
				graph.get(i).add(new StarDist(j, dist));
				graph.get(j).add(new StarDist(i, dist));
			}
		}

		// prim
		double result = 0;
		distance[0] = 0;
		PriorityQueue<StarDist> pq = new PriorityQueue<>();
		pq.add(new StarDist(0, 0));

		while (!pq.isEmpty()) {
			StarDist s = pq.remove();
			if (visited[s.star])
				continue;
                
			visited[s.star] = true;
			result += s.dist;
            
			for (StarDist i : graph.get(s.star))
				if (!visited[i.star])
					if (i.dist < distance[i.star]) {
						distance[i.star] = i.dist;
						pq.add(i);
					}
		}

		// 소수점 둘째 자리까지 출력
		System.out.printf("%.2f", result);
	}

	// 거리 계산
	public static double calDist(Star a, Star b) {
		return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
	}
}

+
これは解答しながら勉強する問題です.実際、私はMSTアルゴリズムについてまだよく知らないので、この問題を解決する過程でprimアルゴリズムに対して明確な総括と理解を持っています.これからもkruskalアルゴリズムで解きます
さらに,数学的相関(平方根/平方根)法も理解し,優先キューも理解した(実際にはソートを直接使用することができる).久しぶりのピタゴラス公式も….ははは
努力して問題を解決したが、他の人よりも足りないようだ.効率が低いと言うべきでしょう...時間とメモリを無駄にしたからです.勉强の段阶なので、自分の力で解决して勉强するのは意味がありますが、やはり少し萎縮している感じがします.私はこの和弦しか編めません.
いやいや、初めてなのでできないのは当たり前!他人のコード分析を見て、改善すればいい!先に出して!成功した!