백준 1197번 최소 스패닝 트리 - Java

 

최소 스패닝 트리

 

 

최소 스패닝 기본 문제이다.

모든 정점이 연결되어야 하고, 각 연결된 간선이 최소값으로만 구성이 되어야 한다.

크루스칼과 프림 알고리즘으로 해결할 수 있는데, 두가지로 풀어보았다.

🔽 알고리즘 차이점 확인

https://hb-in99.tistory.com/191

최소 신장 트리를 위한 프림, 크루스칼 알고리즘

 

 

프림 알고리즘

 

import java.io.*;
import java.util.*;
 
public class Main { // 최소 스패닝 트리
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
 
        // 간선이 아닌 정점의 개수로 변경..
        ArrayList<Node>[] tree = new ArrayList[V + 1];
        boolean[] visited = new boolean[V + 1];
 
        for (int i = 1; i <= V; i++) {
            tree[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            tree[s].add(new Node(e, c));
            tree[e].add(new Node(s, c));
 
        }
 
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));
 
        long answer = 0L;
 
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            if (visited[node.idx]) {
                continue;
            }
            answer += node.cost;
            visited[node.idx] = true;
 
            for (Node next : tree[node.idx]) {
                if (!visited[next.idx]) {
                    pq.add(new Node(next.idx, next.cost));
                }
            }
 
        }
        System.out.println(answer);
 
    }
 
    public static class Node implements Comparable<Node> {
        int idx;
        int cost;
 
        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
 
        @Override
        public int compareTo(Node n1) {
            return Integer.compare(this.cost, n1.cost);
        }
    }
}
 

 

크루스칼 알고리즘

 

import java.io.*;
import java.util.*;
 
public class Main { // 최소 스패닝 트리 - 크루스칼 알고리즘
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
 
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            pq.add(new Node(s, e, c)); //
        }
 
        int[] parent = new int[V + 1];
        int[] rank = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
 
        long answer = 0L;
        int edgesUsed = 0;
 
        while (edgesUsed < V - 1 && !pq.isEmpty()) {
            Node node = pq.poll();
            if (union(parent, rank, node.start, node.end)) {
                answer += node.weight;
                edgesUsed++;
            }
        }
 
        System.out.println(answer);
    }
 
    // Find 연산 경로 압축 기법
    public static int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
 
    // Union 연산 랭크를 활용하여 트리 높이를 최소화
    public static boolean union(int[] parent, int[] rank, int a, int b) {
        int rootA = find(parent, a);
        int rootB = find(parent, b);
 
        if (rootA == rootB) return false; // 이미 같은 집합에 속하는 경우
 
        // 랭크를 기준으로 낮은 트리를 높은 트리 아래에 붙임
        if (rank[rootA] > rank[rootB]) {
            parent[rootB] = rootA;
        } else if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
 
        return true;
    }
 
    public static class Node implements Comparable<Node> {
        int start;
        int end;
        int weight;
 
        public Node(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node n) {
            return Integer.compare(this.weight, n.weight); // 가중치에 따라 비교
        }
    }
}