[문제풀이] 군사도로망

1. 설명

군사도로망

문제

어떤 나라는 NN개의 도시로 구성되어 있다. 도시들을 연결하는 도로들이 있는데, 도로라는 것은 서로 다른 두 도시를 연결하는 기능을 하며, 양방향 통행이 가능하고 하나의 도시 쌍에 대해서는 최대 하나의 도로만이 존재 가능한 것으로 가정한다. 이 나라는 몇 년간 전쟁을 치르고 있어서 많은 도로가 파괴된 상태이다. 이제 도로들을 정비하여 모든 쌍의 도시가 단 하나의 길(길은 이어서 갈수 있는 도로들을 말함)로 연결되도록 하고 싶다. 군사적인 이유로, 두 도시를 연결하는 길이 두 가지 이상 존재하는 것을 원하지 않기 때문이다. 모든 쌍의 도시 사이에 도로를 만들 수 있는 것은 아니라서, 한 쌍의 도시가 있는 경우 이들 사이에는 이미 도로가 존재, 도로를 만드는 것이 가능, 도로를 만드는 것이 불가능한 세가지 경우가 존재할 수 있다. 도로 정비 과정에서 존재하는 도로를 제거해야 하는 경우도 있음에 주의하라. 각 도로는 만들거나 제거할 때는 비용이 발생하며 비용은 도로마다 다를 수 있다. (이 나라는 가상의 세계에 존재하는 것이므로 서로 다른 두 도로가 교차하는 문제는 전혀 고려할 필요가 없다.)

위의 그림에 하나의 예가 제시되어 있다. 왼쪽이 초기 상태인데, 이 나라는 55개의 도시로 구성되어 있으며, 33개의 실선으로 표시된 도로는 기존에 존재하는 것이며, 33개의 점선으로 표시된 도로는 건설이 가능한 것이다. 문제의 조건을 만족하면서 최소의 비용을 지불하는 방법은 도시 11과 22 사이의 도로를 제거하고 (비용 11) 도시 33과 55 사이와 도시 44와 55 사이의 도로를 건설하여 (비용 66), 오른쪽 그림과 같은 상태를 만드는 것이다. 총 비용은 77이 된다. 이 예에서 모든 경우들을 따져 보면 정답은 유일함을 알 수 있다.

도시의 수, 지금 존재하는 MM개의 도로들과 각 도로를 제거하는 비용, 도로를 건설하는 것이 가능한 KK개의 도시의 쌍과 각 도로의 건설 비용을 받아서 위의 목적을 달성하는 비용의 최소값과 그 최소값을 달성하는 방법이 유일한 지를 확인하는 프로그램을 작성하라.

입력

첫 줄에 자연수 세 개가 주어지는데, 첫 수는 N(1≤N≤100,000)N(1≤N≤100,000), 둘째 수는 M(0≤M≤300,000)M(0≤M≤300,000), 셋째 수는 K(0≤K≤300,000)K(0≤K≤300,000)이다. MM이나 KK가 00일 수도 있음에 주의하라. 하지만, 둘 다 00인 경우는 없다. 도시들은 11 부터 NN까지 번호가 붙은 것이다.

이후 MM개의 줄에 기존에 존재하는 각 도로에 대해서 양쪽 끝 도시의 번호와 도로를 제거하는 비용이 33개의 자연수로 주어진다.

이후 KK개의 줄에 건설이 가능한 도로들에 대해서 양쪽 끝 도시의 번호와 건설하는 비용이 주어진다.모든 비용 값은 109109 보다 크지 않은 자연수이며, 항상 목적을 달성할 수 있도록 입력이 주어진다.

출력

첫 줄에 최소 비용의 값을 자연수로 출력한다. 다시 한 칸을 떼고 최소비용을 만든 방법이 유일한 경우 “unique”, 그렇지 않은 경우 “not unique”를 따옴표 제외하고 출력한다.

입력예제

1
5 3 3
1 2 1
1 3 4
2 3 2
3 5 2
3 4 7
4 5 4

출력예제

7

2. 문제풀이

처음에 문제를 봤을때, MST라는 것을 미리 생각하는것이 중요합니다. MST문제의 대부분은 연결을 하되, 싸이클이 생기지 않으면서 동시에 간선의 합이 최소로 가는것입니다.

그런데 이문제를 보면, 연결을 하기만 하는것이 아니고, 연결이 되어있는 것을 없애는 것도 있다.

즉, 연결을 없애는 것 + 연결을 하는것 = 정답 으로 기록하면 됩니다.

좌측으로는 연결되어있는 3개의 노드가 들어와 있고, 오른쪽에는 연결이 가능한 노드들이 있습니다.

크루스칼을 사용할때, 좌측에서는 기존 크루스칼 학습의 반대(간선을 내림차순으로 정렬하고 하나씩 연결하되, 싸이클이 생길떄 마다 간선값 합산)로 계산을 해주고, 오른쪽은 기존방식(간선을 오름차순으로 정렬하고 하나씩 연결하면서 간선값을 합산하고, 싸이클이 생기면 넘어간다)로 정리를 할 수 있습니다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.Vector;

public class MST_군사도로망 {
    static Vector edge1, edge2;
    static int T, n,m,k; // 3, 3
    static long res;     //long 주의
    static boolean chk;
    static int[] parent;

    //크루스칼 객체 (정점에 정보를 저장하는 객체)
    static class kruscal{
        int from, to, val;
        public kruscal(int from, int to, int val) {
            this.from = from;
            this.to = to;
            this.val = val;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        T =  Integer.parseInt(st.nextToken());

        //1. 테스트 케이스
        for (int i = 1; i <= T; i++) {
            res = 0;
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); //정점의 갯수

            m = Integer.parseInt(st.nextToken()); //연결된 갯수
            k = Integer.parseInt(st.nextToken()); //미연결된 갯수

            parent = new int[n+1];
            for (int j = 1; j <= n; j++)
                parent[j] = j;

            //1. 그래프 형성
            edge1 = new Vector();
            for (int q = 0; q < m; q++) {
                st = new StringTokenizer(br.readLine());
                kruscal ks = new kruscal(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                edge1.add(ks);
            }

            edge2 = new Vector();
            for (int w = 0; w < k; w++) {
                st = new StringTokenizer(br.readLine());
                kruscal ks = new kruscal(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                edge2.add(ks);
            }
            //2. 정렬
            Collections.sort(edge1, new Comparator() {
                @Override
                public int compare(kruscal o1, kruscal o2) {
                        if(o1.val < o2.val) return 1;
                        else if(o1.val == o2.val) return 0;
                        else return -1;
                    }
            });
            Collections.sort(edge2, new Comparator() {
                @Override
                public int compare(kruscal o1, kruscal o2) {
                    if(o1.val < o2.val) return -1;
                    else if(o1.val == o2.val) return 0;
                    else return 1;
                }
            });

            ///////////////////////////////////////////////////////////////////////

            //3. 실제 작업.
            for (int a = 0; a < m; a++) {
                merge(edge1.get(a).from, edge1.get(a).to);
                if(!chk)
                    res += edge1.get(a).val;
            }

            for (int b = 0; b < k; b++) {
                merge(edge2.get(b).from, edge2.get(b).to);
                if(chk)
                    res += edge2.get(b).val;
            }
            System.out.println("#" + i + " " + res);

        }
    }
    public static int find(int u){
        if(u == parent[u])
            return u;
        return parent[u] = find(parent[u]);
    }
    public static void merge(int u, int v){
        chk = false;
        u = find(u);
        v = find(v);
        if(u==v) return;
        parent[u] = v;
        chk = true;
    }
}