[Algorithm] 원더랜드_프림 알고리즘(최소스패닝트리)

스패닝 트리란 회로가 존재하지 않도록 그래프의 모든정점을 연결하는 트리이다.

* 회로가 존재한다. == 사이클이 발생한다. == 출발점에서 시작해서 출발점으로 돌아온다. == 그래프

* 아래의 문제 이미지에서 왼쪽 이미지=그래프 / 오른쪽 이미지=트리

 

최소 스패닝 트리(MST)는 스패닝 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 트리를 뜻한다.

 

이번 최소 스패닝 트리 문제는 프림 알고리즘, PriorityQueue을 이용하여 해결 할 것이다.

---

설명

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

아래의 그림은 그 한 예를 설명하는 그림이다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

 

입력

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.

 

출력

모든 도시를 연결하면서 드는 최소비용을 출력한다.

 

예시 입력 / 출력

9 12 1 2 12 1 9 25 2 3 10 2 8 17 2 9 8 3 4 18 3 7 55 4 5 44 5 6 60 5 7 38 7 8 35 8 9 15

196

 

 

 

풀이 과정

- 초기 셋팅 및 프림 알고리즘 시작값 설정

1. 입력받은 값들을 2차원 ArrayList로 인접리스트를 완성한다. (무방향 이므로 두 정점을 각각의 인접리스트로 넣는다.)

2. 정점수 크기를 갖는 배열 ch[ ]를 만든다. (0으로 전부 초기화)

3. 1번 정점부터 시작한다는 전제로 ch[1]에 값 '1'을 넣고 1번 정점의 인접리스트를 값들을 꺼내 PriarityQueue에 담는다. (ch[ ]의 값 = 0은 아직 연결된 간선이 없음 , 1은 연결된 간선이 있음. -> 이것으로 사이클을 확인한다)

 

- 반복(while)

1. PriarityQueue에서 하나씩 꺼낸다. 이떄 cost기준으로 내림차 정렬되어 있어 cost가 가장 저렴한 값을 꺼내게 된다.

꺼낸 값의 정점을 ch배열의 인덱스로 하여 ch[정점]의 값을 '1'로 변경하고

Edge의 비용(cost)를 누적한다. -> 꺼낸 값의 정점으로 연결하는데 가장 저렴한 값이다.

2. 꺼낸 값의 정점을 인덱스로 갖는 n번째 인접리스트를 전부 확인하여 꺼낸 값들의 정점을 인덱스로 갖는

즉 ch[꺼낸 값 정점] 0일 경우만  PriarityQueue에 담는다.

 

풀이

public class Main {

    static class Edge implements Comparable<Edge>{
        int vertex;
        int cost;
        public Edge(int vertex, int cost){
            this.vertex = vertex;
            this.cost = cost;
        }
        @Override
        public int compareTo(Edge o) {
            // 유지비용 오름차 정렬
            return this.cost - o.cost;

        }
    }

    static int v;
    static int e;
    static PriorityQueue<Edge> pQ = new PriorityQueue<>(); // 오름차정렬로 담길 프큐
    static ArrayList<ArrayList<Edge>> arr = new ArrayList<>(); //2차원 ArrayList
    static int[] ch; // 정점 체크 배열 (0 = 연결X, 1 = 연결O)
    static int result = 0;

    static void Solution(int v){ // v == 1 (시작 1번)

		// 시작값 셋팅
        ch[v] = 1; // 여기서 시작하니 해당 인덱스 '1'로 셋팅 후 시작
        for (Edge e : arr.get(v)) pQ.offer(e); // 1번 인덱스의 인접리스트 값 전부 꺼내 담는다.

        while(!pQ.isEmpty()){
            Edge temp = pQ.poll(); // 현재 피큐에 담긴 cost최소값을 하나 꺼낸다. (꺼낸 값 기준 비즈니스 로직 처리)
            if(ch[temp.vertex] == 0){
                ch[temp.vertex] = 1; // 해당 정점 ch 체크
                result += temp.cost; // 해당 유지비용 누적
                for (Edge e : arr.get(temp.vertex)) { // 인접리스트 꺼내 담는다.
                    if(ch[e.vertex] == 0){ // ch배열[꺼낸 값의 정점]값이 '1'이면 이미 연결되어 있으므로 버린다.
                        pQ.offer(e);
                    }
                }
            }
        }
        System.out.println(result);
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        v = sc.nextInt(); // 도시갯수(정점)
        e = sc.nextInt(); // 도로의 갯수(간선)
        ch = new int[v+1];
        for (int i = 0; i <= v; i++) {
            arr.add(new ArrayList<Edge>());
        }
        for (int i = 0; i < e; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int cost = sc.nextInt();
            // 무방향이니 양쪽 다 넣어준다.
            arr.get(v1).add(new Edge(v2, cost));
            arr.get(v2).add(new Edge(v1, cost));
        }
        Solution(1); // 시작은 정점 1부터.
    }
}