[알고리즘] 9-7 원더랜드 - 프림 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07

프림 알고리즘(Prim Algorithm)

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

동작 과정

1. 시작 정점을 최소 신장 트리 집합에 포함한다.
2. 집합에 포함된 정점과 연결된 정점들 중에 최소 비용으로 연결된 정점을 선택하여 연결하여 집합을 확장한다. (단, 회로를 형성하는 이미 집합에 포함된 정점끼리 연결하는 것은 제외)
3. 2번 과정을 최소 신장 트리가 완성될 때까지 반복한다.

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

풀이 코드

• 우선 순위 큐를 사용하여 집합과 최소비용으로 연결된 정점을 찾는다.
• checked 배열을 사용하여 집합에 포함된 정점인지 확인한다.

package inflearn.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//원더랜드(최소 스패닝 트리) - 프림 알고리즘
public class Main9_7_2 {

    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;
        }
    }

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

        int v = Integer.parseInt(st.nextToken()); //도시의 개수
        int e = Integer.parseInt(st.nextToken()); //도로의 개수

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

        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<>());
        }

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

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            //무방향 그래프기 때문에 양방향 모두 연결
            graph.get(a).add(new Edge(b, c));
            graph.get(b).add(new Edge(a, c));
        }

        int sum = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] checked = new int[v+1]; //연결된 정점인지 확인하는 용도
        pq.offer(new Edge(1, 0)); //시작점 큐에 추가

        while (!pq.isEmpty()) {
            Edge findV = pq.poll();

            if (checked[findV.vertex] == 0) {
                checked[findV.vertex] = 1;
                sum += findV.cost;

                for (Edge edge : graph.get(findV.vertex)) {
                    if (checked[edge.vertex] == 0) //이미 지나온 간선을 제외하기 위해
                        pq.offer(edge);
                }
            }
        }

        System.out.println(sum);

        br.close();
    }
}

참고

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html