BOJ - 비용 2463번 (JAVA)

❓ 문제 - 백준 비용 2463번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/2463)

2463번: 비용

 

 

 

📝 문제해결법

1. 문제 해석

• Cost(u, v)는 u와 v사이에 경로가 있으면 이 그래프의 최소 가중치 간선을 그래프에서 제거하는데 u와 v 사이의 경로가 없을 때까지 반복해서 제거하고, 제거되는 간선의 합을 구한다.
• u < v인 모든 두 정 점들의 Cost(u, v)들의 총 합을 출력한다.
• 예를 들어 문제에서 주어진 예시로 cost(2, 6)이라면 정점 2, 6사이에 이어지는 모든 간선들 중 2, 6보다 작은 간선들은 (2,3)-> 3, (4, 3) -> 3,  (3, 5) -> 4, (3, 4) -> 5 이며 이 간선들을 다 제거하고 그 다음 크기의 간선인 2,6까지 지우면 2,6 사이의 경로는 존재하지 않으며, Cost(u, v)는 2+3+4+5+6 = 20으로 구할 수 있다.

 

2. 해결 방법

• u < v 인 모든 두 정점의 Cost(u, v)의 합을 구할 때, 위 방법의 순서대로 하면 하나하나 다 따지면서 계산해야하므로 복잡하다. 따라서 계산은 역방향으로 진행하며, 모든 간선이 떨어져 있다고 가정하고 최대 간선부터 연결하면서 Cost(u, v)를 계산한다.
• 우선 간선을 내림차순으로 정렬한 후, 모든 간선의 합을 구한다.
• 먼저 최대 간선을 연결하고, 간선의 총합을 구한다.

테스트 케이스 예시 1 1) 초기 6개의 정점은 다 분리된 상태에서 시작하며, 모든 간선의 합은 45이다. 2) 먼저 간선의 비용일 기준으로 내림차순을 진행한다. 3) 먼저 최대 간선인 15을 먼저 연결하면 정점 3, 6은 하나의 연결이 되며, union find를 수행해서 서로 같은 부모 3으로 설정한다. Cost(3, 6) = 45이며 이제 남은 간선들의 합은 45-15 = 30이다. 4) 그 다음 최대 간선 10을 연결하면 정점 1, 2는 하나의 연결이 되며 union find를 수행해서 서로 같은 부모 1로 설정한다. Cost(1, 2) = 30이며, 이제 남은 간선들의 합은 30-10 = 20이다. 5) 그 다음 최대 간선 6을 연결하면 1-3 / 1-6 / 2-3 / 2-6 즉 1, 2, 3, 5은 하나로 연결되고 Cost(1, 3) = Cost(1, 6) = Cost(2, 3) = Cost(2, 6) = 20이며 남은 모든 간선의 합은 14이다. . . . 위 과정을 연결되지 않은 남은 간선이 없을 때까지 반복한다.

• 위 과정은 Union-Find 방법으로 하며 두 개의 다른 부모를 바라보면 합집합을 수행하고, 두 개의 그룹에 포함된 정점들을 다 모두 이어주고, 이 두 정점수를 곱한 수와 남은 간서의 합을 곱하면서 모든 Cost(u, v)의 합을 구한다.

 

 

3. 삽질 & 느낀점

• 문제를 40분 넘게 봤는데.. 대충은 이해가 갔는데 어떻게 접근을 해야할지 감이 오지 않았다. 그리고 무언가 연결된 것을 찾아서 값들을 더해주고 하는 것 같아서 Union-Find 방법까지 생각했지만 구현방법을 모르겠었다. 그래서 다른 살마들의 풀이를 보면서 역방향(간선을 이어주는) 방법을 알아냈고 그대로 구현했는데.. 통과했다!
• 문제에서 나열된 계산방법 그대로 구현하려 할 때 너무 복잡하다면 역방향의 계산 방법 들을 고려해보는 방법도 생각해야할 것 같다.

 

💻 소스코드 

// BOJ - 비용(2463번)
// Union find

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

public class Main_2463 {
    public static int n, m;
    public static int[] parent;
    public static int[] child;

    public static class Edge implements Comparable<Edge>{
        int x;
        int y;
        int cost;
        public Edge(int x, int y, int cost){
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return o.cost - this.cost;
        }
    }
    public static ArrayList<Edge> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        long sum = 0;
        list = new ArrayList<>();
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            sum += c;
            list.add(new Edge(Math.min(a, b), Math.max(a, b), c));
        }
        parent = new int[n+1];
        child = new int[n+1];

        for(int i=1;i<=n;i++){
            parent[i] = i;
            child[i] = 1;
        }

        long answer = 0;
        Collections.sort(list);

        for(Edge edge:list){
           answer += sum * union(edge.x, edge.y);
           answer %= 1000000000;
           sum -= edge.cost;
        }

        System.out.println(answer);

    }

    public static int find_parent(int x){
        if(parent[x] == x) return x;
        return parent[x] = find_parent(parent[x]);
    }

    public static long union(int a, int b){
        int parentA = find_parent(a);
        int parentB = find_parent(b);
        if(parentA == parentB) return 0;
        parent[parentB] = parentA;
        long cnt = (long) child[parentA] * child[parentB];
        child[parentA] += child[parentB];
        child[parentB] = 0;
        return cnt;

    }

}