악덕 영주 혜유

---

풀이 방법

MST를 이용해서 모든 마을을 연결할 수 있는 최소 비용을 구해주었다.

그 경로 중 마을과 마을을 이동할 때 최악의 비용이 얼마인지 구해주기 위해 MST를 저장해주었다.

최악의 비용을 구하기 위해서는 임의의 한곳에서 dfs로 가장 먼 노드를 찾아주고 그 노드를 시작으로 dfs를 하면 나오게 된다.

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static int K, N, max, start;
    static int[][] arr;
    static int[][] arr2;
    static boolean[] visited;
    static Queue<Node> pq = new PriorityQueue<>();

    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());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N][N];
        arr2 = new int[N][N];
        visited = new boolean[N];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            arr[a][b] = c;
            arr[b][a] = c;
        }
        visited[0] = true;

        for (int i = 0; i < N; i++) {
            if (arr[0][i] != 0)
                pq.offer(new Node(0, i, arr[0][i]));
        }
        int count = 1;
        int answer = 0;

        while (!pq.isEmpty()) {
            if (count == N) {
                break;
            }

            Node node = pq.poll();

            if (visited[node.a] && visited[node.b])
                continue;

            answer += node.c;
            arr2[node.a][node.b] = node.c;
            arr2[node.b][node.a] = node.c;

            if (visited[node.a] && !visited[node.b]) {
                count++;
                visited[node.b] = true;
                for (int i = 0; i < N; i++) {
                    if (arr[node.b][i] != 0 && !visited[i])
                        pq.offer(new Node(node.b, i, arr[node.b][i]));
                }
            } else if (!visited[node.a] && visited[node.b]) {
                count++;
                visited[node.a] = true;
                for (int i = 0; i < N; i++) {
                    if (arr[node.a][i] != 0 && !visited[i])
                        pq.offer(new Node(node.a, i, arr[node.a][i]));
                }
            }
        }
        max = 0;
        start = 0;

        Arrays.fill(visited, false);
        visited[start] = true;
        dfs(start, 0);

        Arrays.fill(visited, false);
        visited[start] = true;
        dfs(start, 0);


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

    static void dfs(int index, int cost) {
        if (max < cost) {
            max = cost;
            start = index;
        }
        max = Math.max(cost, max);

        for (int i = 0; i < N; i++) {
            if (!visited[i] && arr2[index][i] != 0) {
                visited[i] = true;
                dfs(i, arr2[index][i] + cost);
                visited[i] = false;
            }
        }
    }
}

class Node implements Comparable<Node> {
    int a, b, c;

    public Node(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override
    public int compareTo(Node o) {
        return this.c - o.c;
    }
}