[백준]20010: 악덕 영주 혜유 - JAVA

[백준]20010: 악덕 영주 혜유

20010번: 악덕 영주 혜유

풀이

🪑 MST를 구하는 활용문제이다.

 

문제의 조건들을 정리해보자.

• 마을간 교역로는 양방향이다.
• 모든 마을은 연결되어있다.
• 구하는 값은 MST 비용과 MST 내에서 가장 먼 노드간의 거리이다.

 

🔧 이제 문제 풀이 과정을 생각해 보자.

1. 마을 간 교역로 정보를 입력 받은 후 MST를 구한다. 
2. MST를 저장해 둔 다음 MST를 내에서 DFS로 가장 먼 노드간의 거리를 구한다.
3. 가장 먼 노드간의 거리를 구하기 위해선 먼저, 한 정점에서 가장 먼 노드를 구한 다음 그 정점에서 다시 가장 먼 노드를 구하면 된다. (백준 1167: 트리의 지름 참고)

 

🔹 MST를 구한다.

- MST알고리즘은 대표적으로 prim, kruskal이 있다. 나는 최소 간선 트리로 선택된 간선의 정보를 저장해 주기 위해 kruskal 알고리즘을 사용하였다. 

 

🔹 DFS로 가장 먼 노드간의 거리를 구한다.

- MST로 선택된 간선들의 정보를 가지고 DFS 탐색을 진행한다.

- 가장 먼 노드 사이의 거리를 구하는 방법은 먼저 한 정점에서 가장 먼 노드를 구한 다음, 그 정점에서 다시 가장 먼 노드까지의 거리를 구하면 된다. (백준 1167: 트리의 지름 참고)

- 해당 방법으로 가장 먼 노드간의 거리를 구해주면 된다.

 

코드

import java.util.*;
 
public class Main {
 
    static PriorityQueue<Node> q = new PriorityQueue<>();
    static ArrayList<Node>[] MST;
    static int[] parent;
    static int n, k;
    static boolean[] visited;
    static int max;
    static int startNode;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        k = scan.nextInt();
 
        MST = new ArrayList[n]; //최소 간선 트리 정보를 저장하는 리스트
        for(int i = 0; i < n; i++) {
            MST[i] = new ArrayList<>();
        }
 
        for(int i = 0; i < k; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int cost = scan.nextInt();
            q.offer(new Node(s, e, cost));
        }
        int min = kruskal(); //MST 비용을 구한다.
       
        max = Integer.MIN_VALUE;
        visited = new boolean[n];
        visited[0] = true;
        dfs(0, 0);
 
        max = Integer.MIN_VALUE;
        visited = new boolean[n];
        visited[startNode] = true;
        dfs(startNode, 0);
 
        System.out.println(min);
        System.out.println(max);
    }
 
    public static void dfs(int node, int total) {
        if(max < total) {
            max = total;
            startNode = node;
        }
 
        for(int i = 0; i < MST[node].size(); i++) {
            Node next = MST[node].get(i);
            if(!visited[next.e]) {
                visited[next.e] = true;
                dfs(next.e, total + next.cost);
            }
        }
    } 
 
    public static int kruskal() {
        parent = new int[n];
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
 
        int min = 0;
        while(!q.isEmpty()) {
            Node current = q.poll();
 
            int p1 = find(current.s);
            int p2 = find(current.e);
 
            if(p1 != p2) {
                union(p1, p2);
                MST[current.s].add(new Node(current.e, current.cost));
                MST[current.e].add(new Node(current.s, current.cost));
                min += current.cost;
            }
        }
        return min;
    }
 
    public static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
 
    public static void union(int a, int b) {
        parent[a] = b;
    }
 
    public static class Node implements Comparable<Node> {
        int s;
        int e;
        int cost;
 
        public Node(int s, int e, int cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }
 
        public Node(int e, int cost) {
            this.e = e;
            this.cost = cost;
        }
 
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}