[백준] 14950번 : 정복자

14950번: 정복자

---

[크루스칼]

최소 스패닝 트리를 만드는 문제인데 약간 문제에 낚였다고 해야하나.. "만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 한다." 라는 문장 때문에 항상 부모가 1번 도시와 연결되어있어야 하는 줄 알고 풀었더니 시간이 2s가 넘게 걸렸다. 아무리 생각해도 이건 아닌 것 같아 일반적인 크루스칼 알고리즘 처럼 풀었더니 정답으로 인정되었다.

 

코드로 보는 것이 더 이해가 쉬울 듯 하다.

        int sum = 0;
        int cnt = 0;
        
        while(true) {
            boolean finish = true;

            for (Edge e : list)
                if (!findParent(e.h, e.tg) && (parent[e.h] == 1 || parent[e.tg] == 1)) {
                    sum += e.w + (t * cnt++);
                    union(e.h, e.tg);
                    
                    finish = false;
                    list.remove(e);
                    break;
                }
            if(finish) break;
        }

위 코드를 보면 무한루프를 돌고, 한 도시를 정복할 때 마다 다시 리스트의 처음으로 돌아가 정복할 곳을 탐색한다. 이렇게 하지 않아도 된다는 뜻이다.

        int sum = 0, cnt = 0;
        for (Edge e : list)
            if (!findParent(e.h, e.tg)) {
                sum += e.w + (t * cnt++);
                union(e.h, e.tg);
            }

 

한 도시를 정복할 때 마다 모든 도로에 t만큼 가중치가 더해지니 이 점에 유의하도록 한다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {

    static class Edge{
        int h, tg, w;
        public Edge(int home, int target, int weight){
            h=home;
            tg=target;
            w=weight;
        }
    }

    static int n, m, t;
    static List<Edge> list = new ArrayList<>();
    static int[] parent = new int[10001];

    static int getParent(int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        return a == b;
    }
    static void union(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(a < b) parent[b] = a;
        else parent[a] = b;
    }

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

        IntStream.rangeClosed(1, n).forEach(i -> parent[i] = i);

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int tg = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list.add(new Edge(h, tg, w));
            list.add(new Edge(tg, h, w));
        }

        list.sort((a, b) -> a.w - b.w);

        int sum = 0, cnt = 0;
        for (Edge e : list)
            if (!findParent(e.h, e.tg)) {
                sum += e.w + (t * cnt++);
                union(e.h, e.tg);
            }

        System.out.println(sum);
    }
}