백준 20010 악덕 영주 혜유 (Java)

1. 문제

FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, 교역로는 양 방향으로 이동할 수 있으며, 서로 도달이 불가능한 마을이 없도록 교역로를 건설하여야 한다.

마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 모든 마을과 마을을 최소한의 비용으로 연결하고 그 비용을 구해보자. 또한 혜유는 이때 마을과 마을을 이동하는 가장 최악의 비용이 얼마인지에 관심이 많다. 임의의 두 마을을 이동하는 최단 경로 중 비용이 가장 큰 경로의 비용도 구해보자.

입력

첫 번째 줄에는 마을의 수 N(1 ≤ N ≤ 1,000)과 설치 가능한 교역로의 수 K(1 ≤ K ≤ 1,000,000)가 주어진다.

두 번째 줄부터 K + 1줄에는 서로 다른 두 마을의 번호 a, b (a ≠ b)와 두 마을을 연결하는 비용 c가 주어진다. (1 ≤ c ≤ 1,000,000)

항상 모든 마을을 연결할 수 있는 경우만 입력으로 주어진다, 또한 최소 비용으로 연결하는 방법은 유일하다.

서로 다른 두 마을 사이에 건설할 수 있는 교역로는 최대 하나뿐이다.

마을은 0부터 N - 1 사이의 번호를 갖는다.

출력

첫 번째 줄에는 모든 마을을 연결하는 최소 비용을 출력한다. 

두 번째 줄에는 마을과 마을을 이동하는 비용이 가장 큰 경로의 비용을 출력한다.

 

2. 풀이

 이 문제는 입력에 대해 두 가지 값을 출력해야 한다. 우선 MST를 만들고, 해당 트리에 대해 가장 멀리 떨어져있는 두 노드 사이의 거리를 측정해야 한다. 하나씩 다루어보자.

2-1. MST

    static int[] parent;

	static Queue<Edge> pq;
    
            pq = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.w - o2.w;
            }
        });


        for (int i = 0; i < k; i++) {
            tokenizer = new StringTokenizer(reader.readLine());

            int u = Integer.parseInt(tokenizer.nextToken());
            int v = Integer.parseInt(tokenizer.nextToken());
            int w = Integer.parseInt(tokenizer.nextToken());

            pq.offer(new Edge(u, v, w));
        }

        int cnt = 0;

        //MST 구하기
        while (!pq.isEmpty()) {

            if (cnt == n - 1) {
                break;
            }

            Edge cur = pq.poll();

            if (findP(cur.u) != findP(cur.v)) {
                uni(cur.u, cur.v);
                ans += cur.w;
                cnt++;
                g.get(cur.u).add(new Node(cur.v, cur.w));
                g.get(cur.v).add(new Node(cur.u, cur.w));
            }

        }
        
class Edge {
    int u;
    int v;
    int w;

    public Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
}

 크루스칼 알고리즘을 사용하여 해당 그래프를 구할 수 있다. edge를 비용의 오름차순으로 정렬한 후 parent가 다르면 union 연산을 통해 합쳐준다. 그러면서, 해당 다리의 설치 비용을 추가해준다.

2-2. 가장 큰 비용의 두 노드 사이의 비용

    static List<List<Node>> g;

    static boolean[] visit;
    
    static int farNode = 0;
    static int farDist = 0;
    
    
        //마을과 마을을 이동하는 비용이 가장 큰 경로의 비용

        //0에서부터 가장 먼 노드가 어딘지 확인 -> farNode에 저장
        dfs(0, 0);

        Arrays.fill(visit, false);
        farDist = 0;

        //0에서부터 가장 먼 쪽에서 다시 dfs 수행
        dfs(farNode, 0);
        
        private static void dfs(int i, int curDist) {

        visit[i] = true;

        if (curDist > farDist) {
            farNode = i;
            farDist = curDist;
        }

        List<Node> adjList = g.get(i);

        for (int j = 0; j < adjList.size(); j++) {

            if (!visit[adjList.get(j).v]) {
                visit[adjList.get(j).v] = true;
                dfs(adjList.get(j).v, curDist + adjList.get(j).w);
                visit[adjList.get(j).v] = false;
            }
        }
    }
    
class Node {
    int v;
    int w;

    public Node(int v, int w) {
        this.v = v;
        this.w = w;
    }
}

 이는 아무 노드에서부터 시작하여 dfs를 수행하여 해당 노드에서 가장 비용이 많이 드는 위치의 노드를 구한 뒤, 그 노드에서 다시 dfs를 수행하여 가장 먼 노드의 거리를 구하면 된다.

 

 해당 두 값을 출력하면 정답을 구할 수 있다.

3. 코드 전문

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

public class Main {

    static int n;
    static int k;

    static int[] parent;

    static Queue<Edge> pq;

    static List<List<Node>> g;

    static boolean[] visit;

    static int ans = 0;
    static int ans2 = 0;

    static int farNode = 0;
    static int farDist = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        n = Integer.parseInt(tokenizer.nextToken());
        k = Integer.parseInt(tokenizer.nextToken());

        parent = new int[n];
        visit = new boolean[n];

        initP();

        g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }

        pq = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.w - o2.w;
            }
        });


        for (int i = 0; i < k; i++) {
            tokenizer = new StringTokenizer(reader.readLine());

            int u = Integer.parseInt(tokenizer.nextToken());
            int v = Integer.parseInt(tokenizer.nextToken());
            int w = Integer.parseInt(tokenizer.nextToken());

            pq.offer(new Edge(u, v, w));
        }

        int cnt = 0;

        //MST 구하기
        while (!pq.isEmpty()) {

            if (cnt == n - 1) {
                break;
            }

            Edge cur = pq.poll();

            if (findP(cur.u) != findP(cur.v)) {
                uni(cur.u, cur.v);
                ans += cur.w;
                cnt++;
                g.get(cur.u).add(new Node(cur.v, cur.w));
                g.get(cur.v).add(new Node(cur.u, cur.w));
            }

        }

        //마을과 마을을 이동하는 비용이 가장 큰 경로의 비용

        //0에서부터 가장 먼 노드가 어딘지 확인 -> farNode에 저장
        dfs(0, 0);

        Arrays.fill(visit, false);
        farDist = 0;

        //0에서부터 가장 먼 쪽에서 다시 dfs 수행
        dfs(farNode, 0);

        System.out.println(ans);
        System.out.println(farDist);


    }

    private static void dfs(int i, int curDist) {

        visit[i] = true;

        if (curDist > farDist) {
            farNode = i;
            farDist = curDist;
        }

        List<Node> adjList = g.get(i);

        for (int j = 0; j < adjList.size(); j++) {

            if (!visit[adjList.get(j).v]) {
                visit[adjList.get(j).v] = true;
                dfs(adjList.get(j).v, curDist + adjList.get(j).w);
                visit[adjList.get(j).v] = false;
            }
        }
    }

    private static void initP() {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    static int findP(int k) {
        return parent[k] == k ? k : findP(parent[k]);
    }

    static void uni(int a, int b) {
        int pa = findP(a);
        int pb = findP(b);

        if (pa < pb) {
            parent[pb] = pa;
        } else {
            parent[pa] = pb;
        }
    }
}

class Node {
    int v;
    int w;

    public Node(int v, int w) {
        this.v = v;
        this.w = w;
    }
}

class Edge {
    int u;
    int v;
    int w;

    public Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
}