[백준]6479: 전력난 - JAVA

[백준]6479: 전력난 

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

6497번: 전력난

풀이

방향성이 없는 n개의 간선으로 연결된 m개의 노드 중에서 MST를 비용을 찾는 문제이다. MST를 찾아야 하는것은 맞지만 결과로 반환하는 값은 MST값이 아니다.

 

문제를 읽어보면 결국 최소 비용을 가질 수 있는 불이 켜진 길로만 이동할때 절약할 수 있는 최대 비용을 찾는것이다. 즉, 전체 비용에서 최소비용을 뺀 값이 우리가 구하려고 하는 값이 된다. 그러므로 prim이나 kruskal알고리즘을 사용하여 MST를 구하고, 이를 전체 비용해서 빼 주면 되는 간단한 문제이다.

 

코드

• krukal

import java.util.*;
 
public class Main {
 
    static int m, n;
    static boolean[] visited;
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static int[] parent;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        while (true) {
            m = scan.nextInt();
            n = scan.nextInt();
 
            if(m == 0 && n == 0) System.exit(0);;
 
            int totalCost = 0;
            for (int i = 0; i < n; i++) {
                int s = scan.nextInt();
                int e = scan.nextInt();
                int cost = scan.nextInt();
                totalCost += cost;
                pq.offer(new Node(s, e, cost));
            }
 
            parent = new int[m];
            visited = new boolean[m];
            System.out.println(totalCost - kruskal());
        }
    }
 
    public static int kruskal() {
        for(int i = 0; i < m; i++) {
            parent[i] = i; 
        }
 
        int minCost = 0;
        while(!pq.isEmpty()) {
            Node current = pq.poll(); 
 
            int p1 = find(current.s);
            int p2 = find(current.e);
 
            if(p1 != p2) {
                union(p1, p2);
                minCost += current.cost;
            }
        }
        return minCost;
    }
 
    public static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
 
    public static void union(int a, int b) {
        parent[a] = b;
    }
 
    public static class Node implements Comparable<Node> {
        int s;
        int e;
        int cost;
 
        public Node(int s,int e, int cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}
 

 

• prim

import java.util.*;
 
public class Main {
 
    static int m, n;
    static boolean[] visited;
    static ArrayList<Node>[] list;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        while (true) {
            m = scan.nextInt();
            n = scan.nextInt();
 
            if(m == 0 && n == 0) System.exit(0);;
 
            list = new ArrayList[m];
            for(int i = 0; i < m; i++) {
                list[i] = new ArrayList<>();
            }
 
            int totalCost = 0;
            for (int i = 0; i < n; i++) {
                int s = scan.nextInt();
                int e = scan.nextInt();
                int cost = scan.nextInt();
                list[s].add(new Node(e, cost));
                list[e].add(new Node(s, cost));
                totalCost += cost;
            }
 
            visited = new boolean[m];
            System.out.println(totalCost - prim());
        }
    }
 
    public static int prim() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0));
 
        int minCost = 0;
        while(!pq.isEmpty()) {
            Node current = pq.poll();
 
            if(!visited[current.e]) visited[current.e] = true;
            else continue;
 
            minCost += current.cost;
            for(int i = 0; i < list[current.e].size(); i++) {
                Node next = list[current.e].get(i);
                if(visited[next.e] == false) pq.offer(next);
            }
        }
        return minCost;
    }
 
    public static class Node implements Comparable<Node> {
        int e;
        int cost;
 
        public Node(int e, int cost) {
            this.e = e;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}