hyeoneee's blog

탐욕적인 방법(greedy method) 을 이용하여 

네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

1) cost 기준으로 오름차순 정렬

2) 정렬된 그래프를 기준으로 간선연결

 - 간선은 필요한 간선만 연결
 - 필요한 간선이란? 기 연결된 정점은 해당 간선을 이용해 연결하지 않는다
 즉, 어떤 두 정점이 연결됐는지 안됐는지 확인하는 연산필요 -> union find 이용 
 1) find(a) != find(b) => 연결 (union(a,b))
 2) find(a) = find(b) => 연결 X

    static long kruskal(int startIdx) {
        initParent();
        for (int i = startIdx; i < M; i++) {
            Edge edge = list.get(i);
            if (find(edge.e) == find(edge.s)) { // 같은 그룹이면 연결 안함
                continue;
            }
            union(edge.s, edge.e); // 다른그룹이므로 연결함
        }
        return -1; // 연결 안되어 있음
    }