[백준 / 골드4] 1647 도시 분할 계획 (Java)

크루스칼에서 find()를 수행하며 parent에 넣어주면 더 빠르다.

문제 보기

사용한 것

• MST를 구하기 위한 크루스칼 알고리즘
• root를 저장하기 위한 parent (이어져 있는지 확인)

풀이 방법

• 정점의 개수와 간선의 수를 입력 받고, 모든 간선들을 입력 받아 list에 추가한다.
• Edge의 compareTo를 오버라이딩 하고 낮은 비용 순으로 정렬 한다.
• 최소 비용을 구하기 위하여 비용이 낮은 간선부터 간선의 각 정점들을 union()한다.
• 두 정점의 root를 찾기 위해 find() 한다. 이 때 find()를 수행하며 parent를 저장하면 하나씩 저장하는 것보다 더 빠르다.
• 만약 두 정점의 root가 같으면 사이클이 발생하므로 false를 반환한다.
• 문제에서 두 마을로 분할한다 했으므로 가장 비용이 높은 간선을 빼고 정답을 구한다. (ct == V - 2 까지)

코드

public class Main {

    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int V = Integer.parseInt(line[0]);
        parent = new int[V + 1];
        List<Edge> list = new ArrayList<>();
        int E = Integer.parseInt(line[1]);
        for (int i = 0; i < E; i++) {
            line = br.readLine().split(" ");
            int v1 = Integer.parseInt(line[0]);
            int v2 = Integer.parseInt(line[1]);
            int cost = Integer.parseInt(line[2]);
            list.add(new Edge(v1, v2, cost));
        }

        Collections.sort(list);

        int result = 0;
        int ct = 0;
        for (int i = 0; i < list.size(); i++) {
            Edge edge = list.get(i);

            if (union(edge.v1, edge.v2)) {
                result += edge.cost;

                if (++ct == V - 2) {
                    break;
                }
            }
        }

        System.out.println(result);
    }

    static int find(int v) {
        if (parent[v] == 0) {
            return v;
        }

        return parent[v] = find(parent[v]);
    }

    static boolean union(int v1, int v2) {
        int r1 = find(v1);
        int r2 = find(v2);

        if (r1 == r2) {
            return false;
        }

        parent[r2] = r1;

        return true;
    }
}

class Edge implements Comparable<Edge> {

    int v1;
    int v2;
    int cost;

    public Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }
}