[BOJ6497] 전력난 (크루스칼, 프림, 최소 신장트리, MST)

 

 

---

문제 링크 

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

6497번: 전력난

 

문제 풀이 

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위의 지문이 조금 이해가 안되었는데, 사이클이 발생하는 경우에 대해 설명하는 것으로 이해했다.

 

- 크루스칼/프림 알고리즘 (최소 신장트리,MST) 사용하여 최소 비용을 구한 후 전체 비용과의 차이를 구한다

최대 절약 비용 = 전체 비용 + 최소 연결 비용

 

- 테스트 케이스에 대한 초기화 주의 

- 테스트 케이스 당 결과를 한줄로 출력해야 함

- cost 기준 오름차순 정렬시 O(NlogN)으로 가장 크다

- 비용 최대치는 int 범위내로 문제 지문에 주어진다

 

시간복잡도 

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

 

참고.https://ongveloper.tistory.com/376

[알고리즘] 크루스칼(Kruskal)과 프림(Prim)

 

 

제출 코드

위가 프림, 아래가 크루스칼

 

1) 크루스칼 알고리즘 풀이

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

public class Main {
    
   static StringBuilder sb = new StringBuilder();

    static int n, m;

    static List<Edge> edgeList;

    static int[] parent;

    static int totalCost;

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

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

        @Override
        public int compareTo(Edge edge) {
            if(cost < edge.cost) return -1;
            else if(cost == edge.cost) return 0;
            return 1;
        }
    }


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

        String line;
        while(!"0 0".equals(line = br.readLine())) {
            st = new StringTokenizer(line);
            n = Integer.parseInt(st.nextToken()); // 집의 수(노드)
            m = Integer.parseInt(st.nextToken()); // 길의 수(간선)

            totalCost = 0;
            edgeList = new ArrayList<>();
            for(int i = 1; i <= m; i++) {
                st = new StringTokenizer(br.readLine());

                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                edgeList.add(new Edge(from, to, cost));
                totalCost += cost;
            }

            // 비용 오름차순 정렬
            Collections.sort(edgeList);

            // 부모 노드 초기화
            parent = new int[n + 1];
            for(int i = 1; i <= n; i++) parent[i] = i;

            //크루스칼 알고리즘 수행
            pro();
        }
    }

    static int getParent(int node){
        if(parent[node] == node) return node;

        return parent[node] = getParent(parent[node]);
    }

    static void union(int a, int b) {
        int _a = getParent(a);
        int _b = getParent(b);

        if(_a < _b) parent[_b] = _a;
        else parent[_a] = _b;
    }

    static boolean unionFind(int a, int b) {
        int _a = getParent(a);
        int _b = getParent(b);

        return _a == _b;
    }

    static void pro() {
        int result = 0;
        for(Edge e : edgeList) {
            if(!unionFind(e.from, e.to)) {
                union(e.from, e.to);
                result += e.cost;
            }
        }

        sb.append(totalCost - result).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();

        System.out.println(sb.toString());
    }
}

 

2) 프림 알고리즘 풀이

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

public class Main {
    
   static StringBuilder sb = new StringBuilder();

    static int n, m;

    static int totalCost;

    static List<Edge>[] adj;

    static boolean[] visit;

    static class Edge implements Comparable<Edge> {
        int idx;
        int cost;

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

        @Override
        public int compareTo(Edge edge) {
            return cost - edge.cost; // 오름차순 정렬
        }
    }

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

        String line;

        while(!"0 0".equals((line = br.readLine()))) {
            st = new StringTokenizer(line);
            n = Integer.parseInt(st.nextToken()); // 집의 수(노드)
            m = Integer.parseInt(st.nextToken()); // 길의 수(간선)

            totalCost = 0;
            adj = new ArrayList[n + 1];
            for(int i = 0; i <= n; i++) adj[i] = new ArrayList<>();

            for(int i = 1; i <= m; i++) {
                st = new StringTokenizer(br.readLine());

                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                adj[from].add(new Edge(to, cost));
                adj[to].add(new Edge(from, cost));

                totalCost += cost;
            }

            pro(totalCost);
        }
    }

    static void pro(int _totalCost) {
        visit = new boolean[n + 1];

        Queue<Edge> que = new PriorityQueue<>();
        que.add(new Edge(0, 0)); // 시작 노드를 0으로 고정

        int result = 0;
        while(!que.isEmpty()) {
            Edge cur = que.poll();

            if(visit[cur.idx]) continue;

            visit[cur.idx] = true;
            result += cur.cost;

            for(Edge next : adj[cur.idx]) {
                if(visit[next.idx]) continue;

                que.add(next);
            }
        }

        sb.append(_totalCost - result).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();

        // 결과 출력
        System.out.println(sb.toString());
    }
}