Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

30. 최소 신장 트리

최소 비용으로 그래프의 모든 정점을 연결해 봅시다.

Java / Python

3. 별자리 만들기

4386번

좌표평면에서 MST를 만드는 문제

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

최소 신장 트리 유형 문제이다. 크루스칼 알고리즘을 사용하여 풀 수 있다. 간선들의 리스트를 만들기 위해 모든 별들 간의 거리를 계산한다. 후, 일반적인 최소 신장 트리 유형과 같이 오름차순으로 간선들을 정렬해준다. 간선과 연결된 두 노드의 부모를 비교하여 다를 경우에만 두 노드를 연결한다.

parent를 자기 자신으로 초기화하고, 부모를 찾는 함수 find와 합집합 연산을 해, 같은 부모를 가지도록 하는 union함수를 이용한다.

• Java

Star class : 별의 번호, x 좌표, y 좌표 저장
Edge class : 간선의 정보를 저장, 연결된 별 s, e와 비용 저장
Comparable을 implements, compareTo override

import java.io.*;
import java.util.*;

public class Main {

	static class Star {
		int number;
		double x, y;

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

	static class Edge implements Comparable<Edge> {
		int s, e;
		double cost;

		Edge(int s, int e, double cost) {
			this.s = s;
			this.e = e;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			// Comparable을 통해 정렬 우선순위 (cost 기준)
			return o.cost >= this.cost ? -1 : 1;
		}
	}

	static int[] parent;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		Star[] star = new Star[N];

		parent = new int[N + 1];
		for (int i = 0; i < N; i++) {
			parent[i] = i;
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			double a = Double.parseDouble(st.nextToken());
			double b = Double.parseDouble(st.nextToken());
			star[i] = new Star(i, a, b);
		}

		PriorityQueue<Edge> pque = new PriorityQueue<>();

		for (int i = 0; i < N - 1; i++)
			for (int j = i + 1; j < N; j++)
				pque.offer(new Edge(i, j,
						Math.sqrt(Math.pow(star[i].x - star[j].x, 2) + Math.pow(star[i].y - star[j].y, 2))));

		double cost = 0;
		while (!pque.isEmpty()) {
			Edge now = pque.poll();

			if (find(now.s) != find(now.e)) {
				union(now.s, now.e);
				cost += now.cost;
			}
		}

		bw.write(Math.round(cost * 100) / 100.0 + "\n");
		bw.flush();
		bw.close();
		br.close();
	}

	// x의 부모 찾기
	public static int find(int x) {
		if (x == parent[x])
			return x;

		return parent[x] = find(parent[x]);
	}

	// y 부모를 x 부모로 치환하기 (x > y 일 경우 반대)
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x != y) {
			if (x < y) {
				parent[y] = x;
			} else {
				parent[x] = y;
			}
		}
	}
}

• Python

import sys
import math
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 크루스칼 알고리즘
def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x]) # 부모 테이블 갱신
    return parent[x]

def union(x, y): 
    x = find(x) 
    y = find(y)

    if x == y: # 동일한 집합일 경우
        return

    if x < y:
        parent[y] = x 
    else: 
        parent[x] = y 

N = int(input())
parent = [i for i in range(N+1)]
stars = []
edges = []
result = 0

for _ in range(N):
    x, y = map(float, input().split())
    stars.append((x, y))

# 모든 별들 간에 간선, 비용 계산 저장
for i in range(N - 1):
    for j in range(i+1, N):
        edges.append((math.sqrt((stars[i][0] - stars[j][0])**2 + (stars[i][1] - stars[j][1])**2), i, j))

edges.sort()

for e in edges:
    cost, x, y = e

    if find(x) != find(y):
        union(x, y)
        result += cost

print(round(result, 2))