글 읽기 - 크루스칼 알고리즘을 이용했는데 어디서 틀렸는지 궁금합니다.

hochan333 2년 전 0

어느 부분이 문제인지 알려주시면 감사하겠습니다!

import java.util.*;

class Edge implements Comparable<Edge> {
    public int start, end, cost;

    public Edge(int start, int end, int cost){
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    public int compareTo(Edge other){
        return this.cost - other.cost;
    }
}

public class Main {
    static int V, E;

    //union-find
    static int[] parent;
    static int find(int n){
        if (parent[n] != n){
            parent[n] = find(parent[n]);
        }

        return parent[n];
    }
    static void union(int n, int m){
        int pn = find(n);
        int pm = find(m);

        if (pn <= pm){
            parent[m] = pn;
        }else{
            parent[n] = pm;
        }
    }

    static PriorityQueue<Edge> pq;
    static void getInput(){
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();

        parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;
        pq = new PriorityQueue<>();
        for (int i = 0; i < E; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            pq.add(new Edge(a - 1, b - 1, c));
        }

    }

    public static void main(String[] args) {
        getInput();

        long minCost = 0;
        while (!pq.isEmpty()){

            Edge e = pq.remove();

            // 사이클 존재
            if (find(e.start) == find(e.end)) continue;

            //미존재
            union(e.start, e.end);
            minCost += (long)e.cost;
            System.out.println(Arrays.toString(parent));
        }

        System.out.println(minCost);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

크루스칼 알고리즘을 이용했는데 어디서 틀렸는지 궁금합니다.

hochan333 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말