BOJ - 악덕 영주 혜유 20010번 (JAVA)

❓ 문제 - 백준 악덕 영주 혜유 20010번 - JAVA 풀이법

 

출처 

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

20010번: 악덕 영주 혜유

 

 

 

📝 문제해결법

1. 문제 해석

• 모든 마을과 마을을 최소한의 비용을 연결하는 비용과, 마을과 마을을 이동하는 가장 최악의 비용을 구하여라

 

2. 해결 방법

• MST+DFS로 구하였다.
• 우선 MST에서 union_find을 활용하여 마을과 마을을 최소한의 비용으로 연결하는 크루스칼 알고리즘을 적용한다.
• 그리고 마을과 마을이 최소한으로 연결되면 list에 연결되는 노드와 거리에 대해 저장한다.
• DFS을 2번 실행해서 list를 기반으로 트리의 지름을 구하듯이 0번 노드에서 가장 멀리 있는 노드를 구하고 그 노드에서 가장 멀리 있는 노드까지의 거리를 구하면 마을과 마을을 연결하는 최대의 길이가 된다.
• 이와 관련된 로직과 증명은 백준의 트리의 지름 문제를 (https://developer-ellen.tistory.com/158) 참조하면 좋을 것 같다.

3. 삽질 & 느낀점

• 처음에 MST와 최대 비용으로 연결하는 마을의 길이를 구하려고 했는데 계속 틀리다 보니 문제를 잘못 읽었다
• 최대 비용으로 연결하는 마을의 길이가 아닌 마을과 마을의 최대 길이를 구하는 부분은 MST로 해결이 안되고 DFS로 구해야한다.
• DFS 방법을 계속 생각하다가 방법이 떠오르지 않아서 다른 블로그를 참조했는데... 예전에 풀었던 트리의 지름 문제의 풀이 방법을 근거로 그래프의 끝과 끝의 가장 긴 길이를 구해서 정답으로 출력하면 되는 것이었다.
• 문제를 가장 정확하게 읽는 것이 첫 번째이며, 풀이가 기억 안 날 때는 예전에 풀었던 방법들을 생각해보면서 문제에 접근해야겠다.

 

 

💻 소스코드 (JAVA)

// BOJ - 악덕 영주 혜유(20010번)
// DFS + MST

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_20010 {
    public static int n, m;
    public static int max, max_node;
    public static int INF = (int)1e9;
    public static class Node implements Comparable<Node>{
        int a;
        int b;
        int dis;
        public Node(int a, int dis){
            this.a = a;
            this.dis = dis;
        }
        public Node(int a, int b, int dis){
            this.a = a;
            this.b = b;
            this.dis = dis;
        }
        @Override
        public int compareTo(Node o) {
            return this.dis - o.dis;
        }
    }


    public static int[] parent;
    public static ArrayList<Node>[] list;
    public static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        parent = new int[n];

        ArrayList<Node> edges = new ArrayList<>();
        list = new ArrayList[n];


        for(int i=0;i<n;i++){
            parent[i] = i;
            list[i] = new ArrayList<Node>();
        }


        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 cost = Integer.parseInt(st.nextToken());
            edges.add(new Node(a, b, cost));
        }
        Collections.sort(edges);

        int size = edges.size();
        int min_score = 0;

        for(int i=0;i<size;i++){
            Node node = edges.get(i);
            if(find_parent(node.a) != find_parent(node.b)){
                min_score += node.dis;
                list[node.a].add(new Node(node.b, node.dis));
                list[node.b].add(new Node(node.a, node.dis));
                union(node.a, node.b);
            }

        }
        max = Integer.MIN_VALUE;
        visited = new boolean[n];
        dfs(0, 0);
        max = Integer.MIN_VALUE;
        visited = new boolean[n];
        dfs(max_node, 0);

        System.out.println(min_score);
        System.out.println(max);
    }

    public static void dfs(int x, int dis){
        visited[x] = true;

        if(max < dis){
            max = dis;
            max_node = x;
        }

        for(Node node:list[x]){
            if(!visited[node.a]){
                dfs(node.a, dis+node.dis);
            }
        }
    }

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

    public static void union(int a, int b){
        a = find_parent(a);
        b = find_parent(b);
        if(a < b){
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

}