원더랜드(Kruskal)

yonii·2021년 9월 3일

Minimum Spanning Tree greedy kruskal 알고리즘

Inflearn JAVA 알고리즘 문제풀이 : 코딩테스트 대비

목록 보기

15/20

원더랜드

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

입력 설명

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.

출력 설명

모든 도시를 연결하면서 드는 최소비용을 출려한다.

입력

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

출력

196

틀린 구현 코드

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v = in.nextInt();
        int e = in.nextInt();

        ArrayList<Edge> list = new ArrayList<>();
        //간선 숫자 = 노드 숫자 - 1
        for(int i=0;i<e;i++){
            list.add(new Edge(in.nextInt(),in.nextInt(),in.nextInt()));
        }

        Collections.sort(list); //오름차순 정렬

        ArrayList<Integer> cycleCheck = new ArrayList<>();
        int answer = 0;

        for(Edge edge : list){
            //비용이 적은 간선부터 포함. 사이클 테이블에 포함안된 경우만 add
            if(!(cycleCheck.contains(edge.node1)&&cycleCheck.contains(edge.node2))){
                //둘다 포함이 안된 경우만 사이클 안만듦.
                if(!cycleCheck.contains(edge.node1)) cycleCheck.add(edge.node1);
                if(!cycleCheck.contains(edge.node2)) cycleCheck.add(edge.node2);
                answer += edge.price;
                System.out.println("n1 :"+edge.node1+" n2: "+edge.node2+" price: "+edge.price);
            }
        }

        System.out.println(answer);

    }

    static class Edge implements Comparable<Edge>{
        public Edge(int node1, int node2, int price) {
            this.node1 = node1;
            this.node2 = node2;
            this.price = price;
        }

        int node1;
        int node2;
        int price;

        @Override
        public int compareTo(Edge o) {
            return this.price - o.price; //간선 비용 오름차순 정렬.
        }
    }

입력 :
9 12
1 2 12
1 9 25
2 3 10
2 8 40
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 35

출력 :
216이 나와야하는데, 181 나옴.

문제점:
기존 체크 조건 - Edge에서 node1과 node2가 모두 checklist에 포함 안되었을 경우에 계산.
이런 경우에 모든 노드가 연결안되고 disjoint set이 만들어질 수 있음.
union&find를 쓰지않고 구현하려함.

구현 코드

 static int[] unf;
    static int find(int v){
        if(v==unf[v]) return v;
        else return unf[v]=find(unf[v]);
    }

    static void union(int a,int b){
        int fa = find(a);
        int fb = find(b);
        if(fa!=fb) unf[fa] = fb;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v = in.nextInt();
        int e = in.nextInt();

        unf = new int[v+1];
        for(int i=1;i<=v;i++){
            unf[i] = i;
        }

        ArrayList<Edge> list = new ArrayList<>();
        int answer = 0;
        for(int i=0;i<e;i++){
            list.add(new Edge(in.nextInt(),in.nextInt(),in.nextInt()));
        }

        Collections.sort(list); //오름차순 정렬

        //간선개수 = 노드 개수 - 1
        for(Edge edge : list){
            if(find(edge.node1)!= find(edge.node2)) {
                union(edge.node1, edge.node2);
                answer += edge.price;
            }
        }

        System.out.println(answer);

    }

    static class Edge implements Comparable<Edge>{
        public Edge(int node1, int node2, int price) {
            this.node1 = node1;
            this.node2 = node2;
            this.price = price;
        }

        int node1;
        int node2;
        int price;

        @Override
        public int compareTo(Edge o) {
            return this.price - o.price; //간선 비용 오름차순 정렬.
        }
    }

union&find를 사용해서 각 index에 맞는 대표노드를 확인해서 대표노드가 같지 않을 경우(사이클이 만들어지지 않는 경우)에만 answer에 간선 값 더해줌.