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

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

3
1.0 1.0
2.0 2.0
2.0 4.0

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

3.41

풀이

그래프 문제 중 MST 알고리즘을 이용하는 문제이다. 문제에서 설명하는 별자리의 조건이 그대로 MST의 조건이기 때문이다. Kruskal/Prim 어느 쪽으로 풀어도 상관없지만, 여기에서는 Prim 알고리즘을 이용하였다.

이 문제에서는 그래프의 정점이 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(): 제곱을 구하는 메소드

마지막으로 소수점 둘째 자리까지 출력해야 한다는 거!

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 알고리즘으로도 풀어봐야겠다.
또 수학 관련(제곱근/제곱) 메소드에 대해서도 알 수 있었고, 우선순위 큐에 대해서도 알아볼 수 있었다(사실 그냥 정렬을 써도 괜찮았을 것 같기도 하지만). 오랜만에 피타고라스 공식도...ㅋㅋㅋㅋ

나름대로 열심히 풀긴 했지만 뭔가 다른 사람들보다 부족한 코드인 것 같다. 효율성이 떨어진다고나 할까... 시간도 메모리도 더 많이 잡아먹어서. 일단 공부하는 단계니까 스스로의 힘으로 풀고 공부한 것에 의의를 두는 게 맞긴 하지만, 그래도 좀 위축되는 느낌이다. 나는 이런 코드밖에 못짜나 싶고.

아냐아냐 처음이니까 좀 못하는 게 당연한 거지! 다른 사람들 코드 보고 분석하면서 개선해 나가면 되는 거야! 일단 풀어냈다! 해냈다!