Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

30. 최소 신장 트리

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

Java / Python

4. 우주신과의 교감

1774번

이미 사용된 간선이 있을 때 최소 비용으로 나머지를 완성하는 문제

이번 문제는 우주신들과 연결된 통로들이 존재할 때 ,아직 연결이 되지 않은 우주신들을 연결해, 새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만드는 문제이다.

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

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

• Java

Point class : 번호, x 좌표, y 좌표 저장
Edge class : 간선의 정보를 저장, 연결된 노드(우주신) s, e와 비용 저장

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

public class Main {
	static class Point {
		int number;
		double x, y;

		Point(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;
	static ArrayList<Edge> edgeList;

	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 = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

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

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			double x = Double.parseDouble(st.nextToken());
			double y = Double.parseDouble(st.nextToken());

			points[i] = new Point(i, x, y);
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());

			union(start, end);
		}

		edgeList = new ArrayList<>();
		for (int i = 1; i <= N; i++) {
			for (int j = i + 1; j <= N; j++) {
				double cost = distance(points[i], points[j]);

				edgeList.add(new Edge(points[i].number, points[j].number, cost));
			}
		}
		Collections.sort(edgeList);

		double result = 0;

		for (int i = 0; i < edgeList.size(); i++) {
			Edge edge = edgeList.get(i);
			if (find(edge.s) != find(edge.e)) {
				result += edge.cost;
				union(edge.s, edge.e);
			}
		}

		bw.write(String.format("%.2f", result) + "\n");
		bw.flush();
		bw.close();
		br.close();
	}

	public static double distance(Point p1, Point p2) {
		return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
	}

	// 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

def dist(a, b):
    return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**(1/2)

N,M = map(int,input().split())
point = [] 
parent = [i for i in range(N+1)]
edges = []
result = 0

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

for _ in range(M):
    x, y = map(int, input().split())
    union(x-1, y-1)

# 모든 point 간에 간선, 비용 계산 저장
for i in range(N - 1):
    for j in range(i+1, N):
        edges.append((dist(point[i], point[j]), i, j))

edges.sort(key = lambda x : x[0])

for e in edges:
    cost, x, y = e
    if find(x) != find(y):
        union(x, y)
        result += cost

print('%.2f' %(result))