최소 신장 트리 MST(최소 스패닝 트리, 별자리 만들기)

[최소 스패닝 트리 - 1197]

 

 

* 조건

• 그래프 정보가 주어진다
• 모든 정점을 연결하면서 가중치의 합이 최소가 되는 트리를 그린다(MST)
• MST의 가중치를 출력한다

 

* 알고리즘

• 최소 비용 신장 트리
• 크루스칼 알고리즘

 

* 로직

• 간선에 대한 정보를 담는 객체를 만든다
• 가중치가 작은 순서로 오름차순 정렬한다
• 순서대로 집합관계를 적용한다(Union, Find)
• 다음 간선이 이미 집합에 속한다면 사이클이 생기기 때문에 넘긴다
• 서로 다른 집합이라면 union을 진행하고 비용을 누적한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Problem_1197 {

    static class Edge_1197 implements Comparable<Edge_1197> {
        public int v1,v2;
        public int cost;

        public Edge_1197(int v1, int v2, int cost) {
            this.v1 = v1;
            this.v2 = v2;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge_1197 o) {
            if(this.cost > o.cost) return 1;
            return -1;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        int nodeSize = Integer.parseInt(st.nextToken());
        int edgeSize = Integer.parseInt(st.nextToken());
        int[] parent = new int[nodeSize+1];
        for(int i=1; i<=nodeSize; ++i)
            parent[i] = i;

        Edge_1197[] edges = new Edge_1197[edgeSize];
        for(int i=0; i<edgeSize; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            edges[i] = new Edge_1197(v1, v2, cost);
        }

        //크루스칼
        Arrays.sort(edges);
        int cost = 0;
        for(Edge_1197 edge : edges){
            //같은 집합이라면 사이클이 생기기 때문에
            if(!isSameParent(edge, parent)){
                union(edge, parent);
                cost += edge.cost;
            }
        }

        System.out.println(cost);
    }

    private static void union(Edge_1197 edge, int[] parent) {
        int v1_parent = findParent(edge.v1, parent);

        parent[v1_parent] = edge.v2;
    }

    private static boolean isSameParent(Edge_1197 edge, int[] parent) {
        int v1_parent = findParent(edge.v1, parent);
        int v2_parent = findParent(edge.v2, parent);

        return v1_parent == v2_parent;
    }

    private static int findParent(int node, int[] parent) {
        if(parent[node] == node) return node;
        return parent[node] = findParent(parent[node], parent);
    }
}

 

 

[별자리 만들기 - 4386]

 

 

* 조건

• 별의 개수 n이 주어진다
• 별 각각의 고유 좌표가 실수 형태로 주어진다
• 가중치는 두 별 사이의 거리 값이다
• 가중치 합의 최소 비용을 구한다

 

* 알고리즘

• 최소 비용 신장 트리
• 크루스칼 알고리즘

 

* 로직

• 나올 수 있는 간선의 경우를 모두 구해놓는다 (list에 담음)
• 크루스칼 알고리즘을 적용한다
• 누적된 cost를 출력한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Problem_4386 {

    static int starSize;
    static ArrayList<Edge_4386> list = new ArrayList<>();
    static Node_4386[] nodes;
    static int[] parent;

    static class Edge_4386 implements Comparable<Edge_4386>{
        public int v1, v2;
        public double cost;

        public Edge_4386(int v1, int v2, double cost) {
            this.v1 = v1;
            this.v2 = v2;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge_4386 o) {
            if(this.cost > o.cost) return 1;
            return -1;
        }
    }

    static class Node_4386 {
        public int nodeNum;
        public double x,y;

        public Node_4386(int nodeNum, double x, double y) {
            this.nodeNum = nodeNum;
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        starSize = Integer.parseInt(br.readLine());
        nodes = new Node_4386[starSize];
        for(int i=0; i<starSize; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");

            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());
            nodes[i] = new Node_4386(i, x, y);
        }

        //모든 간선의 가중치 구하기
        for(int i=0; i<starSize; ++i){
            getEdgeCost(i, nodes[i]);
        }

        //크루스칼
        Collections.sort(list);
        parent = new int[starSize];
        for(int i=0; i<starSize; ++i){
            parent[i] = i;
        }

        double cost = 0;
        for(Edge_4386 edge : list){
            if(!isSameParent(edge)){
                union(edge.v1, edge.v2);
                cost += edge.cost;
            }
        }

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

    private static void union(int v1, int v2) {
        int v1_parent = findParent(v1);
        parent[v1_parent] = v2;
    }

    private static boolean isSameParent(Edge_4386 edge) {
        int v1_parent = findParent(edge.v1);
        int v2_parent = findParent(edge.v2);

        return v1_parent == v2_parent;
    }

    private static int findParent(int node) {
        if(parent[node] == node) return node;
        return parent[node] = findParent(parent[node]);
    }

    private static void getEdgeCost(int index, Node_4386 node) {
        for(int i=index+1; i<starSize; ++i){
            double x_pow = (node.x - nodes[i].x) * (node.x - nodes[i].x);
            double y_pow = (node.y - nodes[i].y) * (node.y - nodes[i].y);
            double cost = Math.sqrt(x_pow + y_pow);

            list.add(new Edge_4386(node.nodeNum, nodes[i].nodeNum, cost));
        }
    }
}