[백준] 1647번 - 도시 분할 계획 JAVA 풀이

 

문제

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

문제유형

크루스칼 알고리즘

 

문제 접근

일반적인 크루스칼 알고리즘 문제이다. 모든 집을 사이클이 없도록 연결하고, 연결된 간선 중 가장 비용이 큰 것을 끊어내면 마을은 두 개로 분할된다. 

크루스칼 알고리즘은 유니온파인드를 이용하여 사이클이 없이 트리를 구성하는 알고리즘인데, 모든 간선의 비용에 대해서 오름차순으로 정렬한 후, 가장 간선의 비용이 작은 것부터 union 한다. 만약 union 도중에 같은 루트를 가지는 노드가 존재한다면, 이는 사이클이 생긴다는 뜻이므로 해당 작업을 무시한다.  

문제에서 최단 경로를 필요로 하기 때문에 사이클 없이 연결되는 간선들의 비용을 result에 누적한다.  

간선 비용은 이미 오름차순으로 정렬되어 있기 때문에, 사이클이 생기지 않으면서 가장 마지막에 연결되는 간선의 비용이 가장 큰 값이다. 

 

이슈

알고리즘은 문제가 없는 것 같은데, 계속 런타임 에러 (IllegalArgument) 가 발생했다.

찾아보니 Comparable의 구현체에 return 값이 -1,0,1 을 모두 포함하고 있어야 한댄다. 

원래 짰던 로직에서는 return -1, 1에 대한 처리만 해주고 있어서, distance가 서로 같을 때 0을 리턴한다는 부분을 추가하니 런타임에러가 일어나지 않았다. 

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Node implements Comparable<Node>{
    int a;
    int b;
    int distance;

    public Node(int a, int b, int distance){
        this.a=a;
        this.b=b;
        this.distance =distance;
    }

    @Override
    public int compareTo(Node o) { //오름차순 정렬
        if(distance<o.distance){ return -1;}
        else if(distance==o.distance){ return 0;}
        else return 1;
    }
}

public class Main {

    public static int find(int v){
        if(p[v]==v){
            return v;
        }
        return p[v]= find(p[v]);
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a < b) {
            p[b] = a;
        }else{
            p[a] = b;
        }
    }
    static int V;
    static int E;
    static int[] p;
    static ArrayList<Node> nodes;

    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        String[] input =br.readLine().split(" ");
        V= Integer.parseInt(input[0]);
        E= Integer.parseInt(input[1]);
        p = new int[100003];
        nodes= new ArrayList<Node>();

        for(int i=1; i<=V; i++){
            p[i] = i;
        }
        for(int i=0; i<E; i++){
            input = br.readLine().split(" ");
            nodes.add( new Node(Integer.parseInt(input[0]),Integer.parseInt(input[1]),Integer.parseInt(input[2])));
        }
        //입력받기 끝
        Collections.sort(nodes);
        //오름차순 정렬 끝

        int result = 0;
        int max_e=0;
        for(int i=0; i<nodes.size(); i++){
            Node node = nodes.get(i);

            if(find(node.a)!=find(node.b)){
                result = result + node.distance;
                max_e = node.distance;
                union(node.a, node.b);
            }

        }
        System.out.println(result - max_e);

    }
}