백준 1185 유럽여행.java

문제

누르면 이동합니다

문제 속 힌트

• N개의 나라가 서로 연결된 것을 유지시키면서 ... N-1개의 길만을 남겨야할 것이다.
  • 만드는 그래프는 모든 정점이 연결되어 있으며 사이클이 없는 그래프
• 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법

MST 다

추가 조건

기본적인 MST에서 조건이 추가되었다.

• 길(엣지)을 지날 때 통행료 뿐만 아니라 각 나라(정점)의 입장료가 있다.
• 마지막 나라는 시작 나라이어야 한다
  • 시작한 나라에서 그대로 다시 돌아와야 한다

어떻게 정점에 있는 가중치까지 고려해서 MST를 만들 수 있을까?

풀이 보기

설명

아래 세 가지에 집중해보자.

• N개 정점, N-1개의 간선으로 이루어진 그래프가 만들어진다.
• 그리고 모든 정점이 사이클 없이 연결되어 있다.
• 어떤 시작점에서 출발하더라도 시작점으로 다시 돌아와야 한다.

우선 시작점만 생각해보자.

시작점이 어디고 어디로 가든 다시 돌아와야 한다.

다음 정점에선 어떨까?

앞에서 어떤 경로를 지나왔는지에 관계 없이 왔던 길로 돌아가야 한다.
다시말해서, X정점에서 길을 지나 Y정점에 도착했다면 다시 같은 길을 지나 X로 돌아가야한다.

Y정점에서 다른 길을 통해 X정점으로 돌아가는 길은 없기 때문이다.

문제 아래에 있는 힌트를 그린 그림

예제에서 민식이가 이동한 경로인데 왔던 길을 다시 돌아가는 것을 볼 수 있다.

결론

처음 시작할 때부터 입장료를 받는다는 것을 기억

• X정점의 입장료 + Y정점의 입장료 + 두 정점 사이의 통행료 * 2를 간선의 가중치로 두고 MST를 만들면 된다.
• 또한 어느 정점에서 시작하더라도 위와 같은 형태로 여행해야 하기 때문에 첫 입장료에 따라 총 비용이 달라지게 된다.
• 그러므로 입장료가 가장 싼 정점부터 시작하도록 하자.

코드

public class Main {
    static class Item{
        int from, to, cost;

        public Item(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }
    static int[] nationSet;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        nationSet = new int[n+1];
        for(int i=1;i<=n;i++) nationSet[i] = i;

        int[] fee = new int[n+1];
        int minFee = Integer.MAX_VALUE;
        for(int i=1;i<=n;i++) {
            fee[i] = Integer.parseInt(br.readLine());
            minFee = Math.min(minFee, fee[i]);
        }

        PriorityQueue<Item> pq = new PriorityQueue<>((o1, o2)->{
            return Integer.compare(o1.cost, o2.cost);
        });
        for(int i=0;i<p;i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            cost = fee[from] + fee[to] + cost + cost;

            pq.add(new Item(from, to, cost));
        }

        int ans = 0;
        while(!pq.isEmpty()){
            Item edge = pq.poll();
            if(union(edge.from, edge.to)){
                n--;
                ans += edge.cost;
                if(n == 1) break;
            }
        }
        System.out.println(ans + minFee);
    }

    static int find(int idx){
        if(idx == nationSet[idx]) return idx;
        return nationSet[idx] = find(nationSet[idx]);
    }

    static boolean union(int n1, int n2){
        n1 = find(n1);
        n2 = find(n2);

        if(n1 == n2) return false;

        nationSet[n2] = n1;
        return true;
    }
}