백준 No.1647 도시 분할 계획 - JAVA

문제

 

동물원에서 막 탈출한 우너숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다.

마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을  작성하시오.

 

 

풀이

문제를 대충 읽어봐도 그래프끼리 연결이 되고 모두가 연결이 되어야 하는데 분리시킨다는 말이 좀 걸렸었다.

근데 마지막에 최소라는 말을 듣고 크루스칼 알고리즘으로 신장트리를 만든 후 가장 큰 가중치 값으로 자를려고 했는데 여기서 실수가 가장 큰 가중치 값은 싸이클이 되었을 수도 있던 부분이라 유니온 시키는 가중치들 중에 가장 큰 값을 뺴줘야 하는 것이었다.

 

 

 

크루스칼 알고리즘을 간단하게 다시 보면

 

- 최소 신장 트리를 찾는 알고맂므

- Greedy를 이용하여 가중치 그래프의 모든 정점을 최소 비용을 연결하는 방법을 찾는 것

- 최소 신장트리: 가중치 그래프에서 간선으 가중치 값의 합이 최소가 되고 , 회로가 없이 모든 정점이 연결되어 있는 트리를 뽑아내는 것

- 신장 트리 : 그래프의 모든 정점이 연결되어 있고, 회로가 없는 그래프

 

동작과정

 

- 그래프의 간선들을 가중치를 기준으로 오름차순으로 정렬한다.

- 오름차순으로 정렬된 리스트에서 간선들을 순서대로 하나씩 뽑는다.(낮은 가중치부터)

- 뽑은 간선이 싸이클을 이루지 않는다면 유니온시킨다

 

출

https://developer-hm.tistory.com/117

[알고리즘] 9-7 원더랜드 - 크루스칼 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘

 

 

 

문제에서 코드로 보면

주어진 3가지 값을 Edge클래스를 통해받는다.

가중치를 기준으로 정렬한다. -> 오름차순

입력받은 그래프들을 모두 순회하며 싸이클을 이루는 형태인지 확인한다.

find메소드인데 첫 시작 parent배열은 자기 자신이 부모이고 union메소드를 통해 변경될 경우 end가 start에 부모가 된다.

union을 바뀌게[ 되버리면 해당 메소드에서 재귀를 통해 해당 값을 찾을 수 있다.

union 메소드를 통해 start와 end의 부모를 찾는다. 그러고 end 인덱스에 start값을 대입한다 여기서 start != end는

싸이클 검사다

마지막 답 부분인데 해당 부분에서 최소 신장트리로 연결된 간선 중 가장 큰 가중치를 최소신장트리를 만들 때 사용한 가중치에서 빼버린다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int parent[];

    static ArrayList<Edge> graph = new ArrayList<Edge>();

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        parent = new int[N+1];
        int total =0;
        for (int i = 1; i < N+1 ; i++) {
            parent[i] = i;
        }


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost =Integer.parseInt(st.nextToken());

            graph.add(new Edge(start,end,cost));
        }


        Collections.sort(graph,new Comparator<Edge>(){
            @Override
            public int compare(Edge o1, Edge o2){
                return o1.cost - o2.cost;
            }
        });


        int temp = 0;
        for(Edge edge : graph){

            if(find(edge.start) != find(edge.end)){
                total += edge.cost;
                union(edge.start,edge.end);
                temp = edge.cost;
            }
        }

        System.out.println(total - temp);
    }

    public static int find(int start){

        if(parent[start] == start){
            return start;
        }
        return parent[start] = find(parent[start]);

    }


    public static void union(int start,int end){
        start = find(start);
        end = find(end);

        if(start != end){
            parent[end] = start;
        }
    }


    static class Edge{
        int start;
        int end;
        int cost;


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