[백준] 6497번 - 전력난

 

6497번: 전력난

 

 

 

문제는 전력난에 허덕이는 도시의 시장이 모든 길로 통하도록 하면서 최소 비용으로 가로등을 켤 때 절약할 수 있는 최대 액수를 구하라고 말한다. 문제 조건을 보면 도시는 항상 연결 그래프 형태이고 거리는 양방향 도로이다. 거리가 양방향 그래프이기 때문에 방향은 고려하지 않아도 되기에 무방향 그래프라고 생각해도 된다. 또한 도시상의 모든 길의 거리 합은 2^31 미터 보다 작다고 하였으므로 변수에 int 자료형을 사용해도 문제없다. 

 

집을 정점, 집과 집 사이의 도로를 간선 그리고 가로등을 켜는데 드는 비용이 도로의 길이에 비례하므로 도로 길이를 간선의 가중치로 생각하면, 이 문제를 단순하게 최소 신장 트리 문제로 치환할 수 있다. 

최소 신장 트리를 구하는데 적용할 수 있는 두 가지 알고리즘인 크루스칼 알고리즘과 프림 알고리즘을 사용할 수 있다. 두 알고리즘에 대한 자세한 설명은 아래 글을 참고.

 

최소 신장 트리(Minimum Spanning Tree)

 

 

 

 

 

구현 방법에 있어서는 이전에 풀이한 백준 1197번 최소 스패닝 트리과 크게 다르지 않아 별도로 정리하지는 않겠다. 

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

 

 

 

 

 

크루스칼 알고리즘

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

public class Main {
    
    // 모든 정점에 대한 부모 노드를 저장
    static int[] parent;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringBuilder sb = new StringBuilder();
        
        while (true) {
            String[] input = br.readLine().split(" ");
            
            int m = Integer.parseInt(input[0]);
            int n = Integer.parseInt(input[1]);
            
            if (m == 0 && n == 0) break;
            
            List<int[]> list = new ArrayList<>();
            parent = new int[m+1];
            for (int i=0; i<m; i++) parent[i] = i;  
            for (int i=0; i<m; i++) list = new ArrayList<>();
            
            for (int i=0; i<n; i++) {
                input = br.readLine().split(" ");
                int from = Integer.parseInt(input[0]);
                int to = Integer.parseInt(input[1]);
                int cost = Integer.parseInt(input[2]);
                list.add(new int[]{from, to, cost});
            }
            
            Collections.sort(list, (a, b) -> {
                return a[2] - b[2];
            });
            
            
            // 절약할 수 있는 거리
            int totalSave = 0;
            for (int[] info : list) {
                
                int from = info[0];
                int to = info[1];
                int cost = info[2];
                
                int fromParent = findParent(from);
                int toParent = findParent(to);
                
                if (fromParent == toParent) {
                	// 만약 부모 노드가 같다면 해당 도로에는 가로등을 켤 필요가 없으므로 불을 켜지 않아도 되는 도로 길이를 더한다.
                    totalSave += cost;
                    continue;
                }
                
                parent[toParent] = fromParent;
            }
            
            sb.append(totalSave + "\n");
        }
        
        System.out.println(sb);
        
        br.close();
    }
    
    
    // 부모노드를 찾고 매개변수로 들어온 정점의 부모노드가 자기 자신이 아닌 경우 부모 노드 최신화
    static int findParent (int node) {
        if (parent[node] == node) return node;
        return parent[node] = findParent(parent[node]);
    }
}

 

 

 

 

 

프림 알고리즘

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

public class Main {
    
    static int[] parent;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        while (true) {
        	
        	PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> {
        		return a[1] - b[1];
        	});
        	
            String[] input = br.readLine().split(" ");
            
            int m = Integer.parseInt(input[0]);
            int n = Integer.parseInt(input[1]);
            
            if (m == 0 && n == 0) break;
            
            boolean[] visited = new boolean[m];
            List<int[]>[] 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++) {
                input = br.readLine().split(" ");
                int from = Integer.parseInt(input[0]);
                int to = Integer.parseInt(input[1]);
                int cost = Integer.parseInt(input[2]);
                list[from].add(new int[]{to, cost});
                list[to].add(new int[]{from, cost});
                totalCost += cost;
            }
            
            
            
            que.offer(new int[]{0, 0});
            
            // 최소 비용으로 가로등을 켠 경우의 도로 길이
            int lampCost = 0;
            while (!que.isEmpty()) {
                
                int[] node = que.poll();
                
                if (visited[node[0]]) continue;
                
                int now = node[0];
                int cost = node[1];
                
                // 새롭게 방문한 노드라면 해당 간선의 도로 길이를 추가한다. 최소 신장 트리 특성에 의해 반드시 켜야 하는 도로 길이만 추가됨
                visited[now] = true;
                lampCost += cost;
                
                for (int[] next : list[now]) {
                	if (!visited[next[0]]) 
                		que.offer(next);
                }
            }
            
            // 총 도로 길이에서 반드시 켜야 하는 도로의 길이를 뺀 결과를 출력
            sb.append(totalCost - lampCost + "\n");
        }
        
        System.out.println(sb);
        
        br.close();
    }
}

 

 

 

 

 

유사문제

1197번: 최소 스패닝 트리