백준 1185 (유렵여행) - java

https://www.acmicpc.net/problem/1185

1185번: 유럽여행

 

문제

민식이는 여름에 유럽여행을 떠날 계획이다. 방문할 나라는 총 N개의 나라이고 편리하게 1번부터 N번까지 번호를 붙였다. 또한 이 나라들 사이에 이동 가능한 길은 M개가 있는데 민식이는 귀찮기 때문에 N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야할 것이다.

각 길을 통과하기 위한 비용이 각기 다르고 한 나라를 도착하면 내야할 비용 역시 나라마다 다르게 정해져있다. 민식이는 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다. 물론 길과 나라는 여러 번 방문할 수 있고, 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라이어야 한다. 이러한 민식이의 유럽 계획을 도와주자. 

 

유형 : MST

 

접근 방식

• '즉, N-1개의 길만을 남겨야할 것이다.' 라는 지문을 보고 결국 N-1 개의 간선으로 전부 순회해야 한다.
• 즉 MST를 만들어야 한다는 것이다.
  • 위 문제에서 고려해야 할 점은 2가지이다.
    • 간선을 선택하는 비용의 기준
    • 전부를 순회하는 값이란 ? 
• 순회
  
  • 순회의 개념이 무엇인지 아는 것이 문제를 푸는 핵심이다. MST를 만들었을 때 시작점을 기준으로 모든 정점을 순회하고 다시 시작점으로 돌아오기 위해서는 선택한 간선을 전부 2번 지나게 된다.
  • 즉 선택한 간선들을 2번 지나는 값 + 시작점의 값이 정답이 된다.
• 간선을 선택하는 기준
  • 우선 순회의 개념을 알았다면 해당 간선을 2번 지나게 된다는 것을 이해했다는 것이다. 하지만 1 -> 2와 2 -> 1의 값이 다르다. 각 정점에 부여된 값이 다르기 때문이다. 하지만 해당 간선을 오고 가고 무조건 그 연산을 수행하기 때문에 모든 경우를 고려하여 우선순위를 정해야 한다.
  • 간선의 값 * 2 + 정점 1의 값 + 정점 2의 값이 우선순위 큐의 가중치가 되는 것이다.

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {
    static int n = 0;
    static int m = 0;

    static int[] root;
    static int[] boardCost;

    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        root = new int[n+1];
        boardCost = new int[n+1];
        for(int i=1;i<=n;i++){
            int tmp = Integer.parseInt(bf.readLine());

            boardCost[i] = tmp;
            root[i] = i;

            min = Math.min(min,boardCost[i]);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (x,y) -> x[2] - y[2]
        );

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(bf.readLine(), " ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            int[] tmp = new int[3];
            tmp[0] = v1;
            tmp[1] = v2;
            // 비용의 개념 : 정점 2개의 값 + 왔다 갔다를 고려한 간선의 값 * 2
            tmp[2] = 2*c + boardCost[v1] + boardCost[v2];

            pq.add(tmp);
        }

        int total = 0;
        int count = 0;

        while(!pq.isEmpty()){
            int[] cur = pq.poll();

            if(find(cur[0]) != find(cur[1])){
                union(cur[0],cur[1]);
                total += cur[2];
                count += 1;
                
            }

            if(count == n-1)
                break;
        }
        
        // 처음 시작하는 위치의 값 + 전체 순환 값
        System.out.println(total + min);
        bf.close();
    }


    static int find(int x){
        if(x == root[x])
            return x;

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;
        else
            root[x] = y;
    }
}