[백준 / BOJ] 20010 악덕 영주 혜유 (Java)

문제

출처 : https://www.acmicpc.net/problem/20010

20010번: 악덕 영주 혜유

N개의 마을과 마을을 연결하는 K개의 간선이 주어진다. 이때, K개의 간선을 이용해서 모든 마을을 연결하는 최소비용과 이때 마을사이를 연결하는 거리의 최댓값을 구하는 문제이다.

---

풀이

최소스패닝트리 알고리즘과 트리의 지름을 구하는 알고리즘을 각각 사용해서 푸는 문제다.

두 알고리즘을 섞어서 사용할 필요는 없고, "모든 마을을 연결하는 최소비용"을 MST를 이용해서 구한후, MST를 진행하며 만들어진 트리 구조에 트리의 지름을 구하는 알고리즘을 적용해서 "마을 사이를 연결하는 거리의 최댓값"을 구해주면 된다.

 

알고리즘은 다음과 같다.

1. 0번 엣지부터 시작해서 모든 엣지에 대해서, MST를 수행한다. 이 때, 2번 과정을 위해서 트리구조를 만들어야한다.

2. 만들어진 트리구조에서 트리의 지름을 구하는 알고리즘을 수행한다. 트리의 지름을 구하는 알고리즘은 다음과 같다.

2-1. 트리에 속한 임의의 정점 A에 대해서 가장 먼 거리의 리프 정점 S를 구한다.

2-2. (2-1)에서 구한 정점 S에 대해서, 가장 먼 리프 정점 E를 구한다.

2-3. 정점 S와 E사이의 거리가 트리의 지름이 된다.

 

위 알고리즘을 그대로 수행하면 답이 나온다.

 

주요 소스코드

 

MST

    private void doSpanningTree(){
        PriorityQueue<Bridge> bridges = initFirstBridges();
        boolean[] visited = new boolean[N];
        visited[0] = true;
        int cost = 0;
        while(!bridges.isEmpty()){
            Bridge bridge = bridges.poll();
            if(visited[bridge.to]) continue;
            visited[bridge.to] = true;
            tree.get(bridge.from).add(new Bridge(bridge.from, bridge.to, bridge.cost));
            tree.get(bridge.to).add(new Bridge(bridge.to, bridge.from, bridge.cost));
            bridges.addAll(edges.get(bridge.to));
            cost += bridge.cost;
        }
        System.out.println(cost);
    }

 

트리의 지름 구하기

    private int getMaxTreeSize(int befIdx, int idx, int cost){
        if(befIdx == idx) return 0;
        if(tree.get(idx).size() == 1 && befIdx != -1) return cost;
        int ans = 0;
        for(int i = 0; i < tree.get(idx).size(); i++){
            int nextIdx = tree.get(idx).get(i).to;
            if(nextIdx == befIdx) continue;
            ans = Math.max(ans, getMaxTreeSize(idx, nextIdx, cost + tree.get(idx).get(i).cost));
        }
        return ans;
    }

---

주요 소스코드

https://github.com/devxb/JJUNalgo/blob/master/20010%20악덕%20영주%20혜유/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃