[알고리즘] 3124. 최소 스패팅 트리

 

0. 문제

 

SW Expert Academy

 

---

1. 문제 이해

 

1. 최소 신장 트리 (MST)
2. Kruskal
3. Prim

 

---

2. 제출

 

MST를 구하는 문제다.

 

주어지는 가중치가 크기 때문에 overflow를 주의하면서 풀면 된다.

 

---

가. Kruskal

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

public class SWEA3124 {

    static int V, E; 
    static long ret; // int overflow 발생
    static int[] p; // 노드의 부모 노드 인덱스를 저장
    static Edge[] edgeList;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st  = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();

        int T = Integer.parseInt(st.nextToken());

        for(int tc=1; tc<=T; ++tc) {
            st  = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            ret = 0; // MST의 최소 비용

            // 간선 리스트 초기화
            edgeList = new Edge[E];
            int from, to, weight;
            for(int i=0; i<E; i++) {
                st  = new StringTokenizer(br.readLine());
                from = Integer.parseInt(st.nextToken());
                to = Integer.parseInt(st.nextToken());
                weight = Integer.parseInt(st.nextToken());
                edgeList[i] = new Edge(from, to, weight);
            }
            Arrays.sort(edgeList);

            // Union-Find을 활용한 MST의 최소 비용 구하기
            make();
            int cnt = 0;
            for(Edge edge : edgeList) {
                if(!union(edge.from, edge.to)) continue;
                ret += edge.weight;
                if(++cnt > V-1) break;
            }

            sb.append("#").append(tc).append(" ").append(ret).append("\n");
        }
        System.out.println(sb);
        br.close();
    }

    static void make() {
        p = new int[V+1]; // 1 ~ V
        for(int i=0; i<V; i++) {
            p[i] =i;
        }
    }

    static int find(int x) {
        return (x==p[x]) ? x : (p[x] = find(p[x]));
    }

    static boolean union(int x, int y) {
        x = find(x);
        y = find(y);

        if(x == y) return false;
        p[y] = x;
        return true;
    }

    static class Edge implements Comparable<Edge>{
        int from, to, weight;

        public Edge(int from, int to, int weight) {
            super();
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

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

    }

}

• static long ret; : int overflow 발생.

 

---

나. Prim - PQ

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

// PQ를 활용한 Prim algorithm으로 구현하기
public class SWEA3124_2 {

    static int V, E;
    static List<Vertex>[] g;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();

        int T = Integer.parseInt(st.nextToken());
        for(int tc=1; tc<=T; tc++) {
            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());

            // 인접 리스트 초기화
            g = new List[V+1]; // 1 ~ V
            for(int i=1; i<=V; i++) {
                g[i] = new ArrayList<>();
            }
            int A, B, C;
            for(int i=0; i<E; i++) {
                st = new StringTokenizer(br.readLine());
                A = Integer.parseInt(st.nextToken());
                B = Integer.parseInt(st.nextToken());
                C = Integer.parseInt(st.nextToken());
                g[A].add(new Vertex(B, C));
                g[B].add(new Vertex(A, C));
            }

            // 최소 신장 트리의 비용 구하기
            long ret = solve();
            sb.append("#").append(tc).append(" ").append(ret).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    static long solve() {
        boolean[] vis = new boolean[V+1];
        int[] D = new int[V+1];
        Arrays.fill(D,  Integer.MAX_VALUE);
        D[1] = 0;

        PriorityQueue<Vertex> pq = new PriorityQueue<>();
        pq.offer(new Vertex(1, D[1]));

        Vertex cur;
        int cnt = 0;
        long ret = 0;
        while(!pq.isEmpty()) {
            cur = pq.poll();
            if(vis[cur.no]) continue;

            vis[cur.no]=true; 
            ret += D[cur.no];
            if(++cnt == V) break;

            for(Vertex vertex : g[cur.no]) {
                if(vis[vertex.no]) continue;
                if(D[vertex.no] > vertex.weight) { // D에 저장된 기존의 비용보다 작은 새로운 비용이 있다면...
                    D[vertex.no] = vertex.weight; // D를 갱신하고
                    pq.offer(vertex);// PQ에 삽입한다.
                }
            }
        }
        return ret;
    }

    static class Vertex implements Comparable<Vertex> {
        int no, weight;

        Vertex (int no, int weight){
            this.no = no;
            this.weight = weight;
        }

        @Override
        public int compareTo(Vertex o) {
            return Integer.compare(this.weight, o.weight);    
        }
    }

}

• static long ret; : int overflow 발생.

 

---