[BOJ] 16398 : 행성 연결(Java)

문제 링크

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

16398번: 행성 연결

💡 풀이

모든 행성 간의 연결을 시도했을 때, 연결 비용을 최소화하는 문제입니다. 즉, 최소 신장 트리(MST)를 떠올릴 수 있습니다. 

최소 신장 트리는 크루스칼 알고리즘, 프림 알고리즘 두 가지로 해결할 수 있습니다. 결론만 얘기하자면, V를 정점의 개수, E를 간선의 개수라 했을 때 각각의 시간 복잡도는 다음과 같습니다.

• 크루스칼 알고리즘 : O(ElogE)
• 프림 알고리즘 : O(ElogV)

즉, 간선의 개수에 따라 간선의 수가 적다면 크루스칼 알고리즘, 간선의 수가 많다면 프림 알고리즘을 사용하는 것이 효율적입니다. 

 

저는 이 문제에서 프림 알고리즘을 사용해 MST를 구현했습니다. 

실제로, 이 문제를 크루스칼과 프림 알고리즘 모두 구현해 비교해보면 프림 알고리즘으로 구현한 코드가 훨씬 빠릅니다. 

프림 알고리즘 (Prim Algorithm)

프림 알고리즘은

임의의 시작점에서 현재까지 연결된 정점들에서 연결되지 않은 정점들에 대해, 가장 가중치가 작은 정점을 연결하는 정점 선택 기반으로 동작합니다.

우선순위 큐를 이용한 최소 힙으로 구현할 수 있습니다. 다익스트라 알고리즘과 구현 방식이 비슷합니다. 

 

 

전체 코드

전체적인 코드는 다음과 같습니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Q16398 {
    static int N;
    static List<List<Edge>> graph = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        initInput();

        System.out.println(prim());
    }

    static void initInput() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        initGraph();
        visited = new boolean[N];

        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < N; x++) {
                int weight = Integer.parseInt(st.nextToken());
                graph.get(y).add(new Edge(x, weight));
            }
        }


    }

    static long prim() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        long result = 0;
        int count = 0;

        pq.add(new Edge(0, 0));

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();

            if(visited[edge.node])
                continue;

            visited[edge.node] = true;
            result += edge.weight;

            for (Edge next : graph.get(edge.node)) {
                if(!visited[next.node])
                    pq.add(next);
            }

            // 모든 정점을 방문했을 경우, 종료
            if(++count == N)
                break;
        }

        return result;
    }

    static void initGraph() {
        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }
    }

    static class Edge implements Comparable<Edge> {
        int node;
        int weight;

        Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

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