[백준 6497] - 전력난

 

문제

• 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다.
  • 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다.
  • 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.
• 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다.
  • 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.
• 위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

 

입력

• 입력은 여러 개의 테스트 케이스로 구분되어 있다.
• 각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)
• 이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)
• 도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.
• 입력의 끝에서는 첫 줄에 0이 2개 주어진다.

 

출력

• 각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

 

 

솔루션

• 최소 스패닝 트리를 사용하는 간단한 문제이다.
  
  • 크루스칼과 프림이 있는데 여기서는 크루스칼을 이용했다.
• 문제를 풀면서 한 가지 유의해야 할 점은 스패닝 트리를 이루는 간선의 총 비용을 구하는 것이 아니라 전체 간선의 총 비용에서 스패닝 트리를 이루는 간선의 비용을 빼서 나온 값을 구해야 한다.

 

Code

• 전체 코드 : Solution_6497

각 노드의 루트 노드를 본인으로 초기화하는 함수

public static void Initialize(int m) {
    for (int i = 0; i < m; i++)
        parent[i] = i;
}

 

노드가 속한 집합의 루트 노드를 찾는 함수

public static int Find(int u) {
    if (parent[u] == u)
        return u;
 
    return parent[u] = Find(parent[u]);
}

 

각 노드가 속한 집합을 합치는 합집합 연산 함수

public static void Union(int u, int v) {
    int uR = Find(u);
    int vR = Find(v);
 
    if (uR == vR)
        return;
 
    if (rank[uR] > rank[vR])
        Swap(uR, vR);
 
    parent[uR] = vR;
 
    if (rank[uR] == rank[vR])
        rank[uR]++;
}

 

간선 객체를 생성하는 클래스

public static class Edge implements Comparable<Edge> {
    int from, to, cost;
 
    public Edge(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
 
    public int compareTo(Edge e) {
        return this.cost - e.cost;
    }
}

 

크루스칼 알고리즘

public static int Kruskal(int n, int total) {
    int cost = 0, count = 0;
 
    while (!edgelist.isEmpty()) {
        Edge edge = edgelist.poll();
        
        if(count == n - 1)
            break;
 
        if (Find(edge.from) != Find(edge.to)) {
            Union(edge.from, edge.to);
            cost += edge.cost;
            count++;
        }
    }
 
    return total - cost;
}

 

메인 함수

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    while (true) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        if(m == 0 && n == 0)
            break;
 
        parent = new int[m];
        rank = new int[m];
        edgelist = new PriorityQueue<>();
 
        Initialize(m);
        
        int total = 0;
 
        for (int i = 0; i < n; 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.offer(new Edge(from, to, cost));
            total += cost;
        }
 
        bw.write(Kruskal(n, total) + "\n");
    }
 
    bw.flush();
    bw.close();
    br.close();
}

 

결과