[Java] 백준 16398번 : 행성 연결*

1. 문제

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

16398번: 행성 연결

 

 

2. 풀이 과정

MST 문제이고, kruskal와 prim이 떠올랐다.

두 가지 알고리즘을 각각 사용해서 두 번 풀어봤는데, 간선의 개수가 많기 때문에 kruskal보다 prim이 훨씬 빨랐다.

 

1. Kruskal

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

public class Main {
    static int N, p[];
    public static PriorityQueue<Edge> edges;

    public static class Edge implements Comparable<Edge> {
        int n1, n2, cost;

        public Edge(int n1, int n2, int cost){
            this.n1 = n1;
            this.n2 = n2;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }

    public static int find(int n1){
        if(p[n1]==0){
            return n1;
        }
        return p[n1] = find(p[n1]);
    }

    public static boolean union(int n1, int n2){
        n1 = find(n1);
        n2 = find(n2);
        if(n1 != n2){
            p[n2] = n1;
            return true;
        }
        return false;
    }

    public static long kruskal(){
        int cnt = 0;
        long result = 0;

        while(!edges.isEmpty()){
            Edge edge = edges.poll();
            if(union(edge.n1, edge.n2)){
                result += edge.cost;
                if(++cnt==N-1){break;}
            }
        }
        return result;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        edges = new PriorityQueue<>();
        p = new int[N+1];
        int idx = 0;
        for(int i=1; i<=N; i++){
            String input[] = br.readLine().split(" ");
            for(int j=i+1; j<=N; j++){
                edges.add(new Edge(i, j, Integer.parseInt(input[j-1])));
            }
        }
        System.out.println(kruskal());
    }
}

 

결과

 

 

2. Prim

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

public class Main {
    static int N, map[][];

    public static long prim(){
        boolean visited[] = new boolean[N];
        long result = 0;
        visited[0] = true;
        for(int i=0; i<N-1; i++){
            int next = 0, min = 999_999_999;
            for(int a=1; a<N; a++){
                if(!visited[a] && map[0][a] < min){
                    min = map[0][a];
                    next = a;
                }
            }

            visited[next] = true;
            result += min;

            for(int a=1; a<N; a++){
                map[0][a] = Math.min(map[0][a], map[next][a]);
            }
        }

        return result;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(prim());
    }

}

 

결과