백준 1647 (도시 분할 계획)

문제

1647번: 도시 분할 계획

임의의 두 노드에서 모두 도달할 수 있는 그래프가 주어지고 각 노드 사이에는 비용이 있는 간선이 주어진다.

이 때 그래프를 둘로 나눈다. 나눈 각각의 그래프는 서로 연결되어 있어야 하고 간선의 합이 최소여야 한다.

두 그래프의 각각의 간선의 합이 최솟값을 구해라.

그래프는 최소 1개의 노드가 존재해야 한다.

---

문제를 잘보면 크루스칼 알고리즘을 사용하는 것을 알 수 있다.

하지만 어떻게 2개로 나눌까??

 

잘 생각해보면 간단하다.

결국 그래프 간선의 합이 최소인것을 구하면 된다.

따라서 모든 노드를 크루스칼로 연결해주고 마지막 노드랑 연결된 간선만 제거해 주면 된다.

List<Integer>edge = new ArrayList<>(); //간선 정보 넣어주기
        for(Info i : list){
            int a = i.a;
            int b = i.b;

            if(find(a) != find(b)) {
                union(a, b);
                edge.add(i.cost);
            }

        }

        for(int i=0;i<edge.size()-1;i++)ans+=edge.get(i);
        System.out.println(ans);

위 코드는 크루스칼 알고리즘을 수행하는 부분이다.

그래프를 연결해주면서 간선의 정보를 edge에 넣어준다.

마지막에 edge에서 for문을 돌면서 edge.size - 1 만큼 누적으로 합해준다.

마지막으로 연결된 간선을 뺴줘야 하기 때문이다.

---

public class Main{
    private static int [] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        parent = new int[n+1];
        Set<Integer> set = new HashSet<>();
        for(int i=1;i<=n;i++){
            parent[i] = i;
            set.add(i);
        }

        List<Info> list = new ArrayList<>();
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.add(new Info(a, b, c));
        }

        Collections.sort(list);

        int ans = 0;

        List<Integer>edge = new ArrayList<>();
        for(Info i : list){
            int a = i.a;
            int b = i.b;

            if(find(a) != find(b)) {
                union(a, b);
                edge.add(i.cost);
            }

        }

        for(int i=0;i<edge.size()-1;i++)ans+=edge.get(i);
        System.out.println(ans);
    }
    private static int find(int u){
        if(parent[u]== u)return u;
        return parent[u] = find(parent[u]);
    }
    private static void union(int a, int b){
        a = find(a);
        b = find(b);

        if(a== b)return;
        parent[a] = b;
    }
}
class Info implements Comparable<Info>{
    int a;
    int b;
    int cost;
    Info(int a, int b, int cost){
        this.a = a;
        this.b = b;
        this.cost = cost;
    }

    @Override
    public int compareTo(Info i){
        return this.cost - i.cost;
    }
}