백준 1197 (최소 스패닝 트리) - java

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

1197번: 최소 스패닝 트리

MST를 구하는 가장 정석적인 방법에는 두가지가 있다.

• 크루스컬 알고리즘
• 프림 알고리즘

이번에는 해당 문제를 프림 알고리즘을 사용하여 해결해보았다.

프림 알고리즘으로 최소 스패닝 트리를 구할때는 습관적으로 우선순위 큐(min heap)을 사용하도록 하자

시간복잡도가 우선순위 큐를 사용할 경우에는 O(ElogV) 이고 배열은 O(V^2)이다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n = 0;
    static int m = 0;


    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()); // 간선

        boolean[] visit = new boolean[n+1]; // 방문 배열
        ArrayList<Edge>[] graph = new ArrayList[n+1]; // 그래프
        for(int i=1;i<=n;i++)
        {
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int last = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[start].add(new Edge(last,cost));
            graph[last].add(new Edge(start,cost)); // 그래프 만들기

        }

        prim(graph, visit);
        br.close();
    }

    static void prim(ArrayList<Edge>[] graph, boolean[] visit)
    {
        int result = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>(
                (x,y) -> x.cost - y.cost
        ); // 간선의 가중치를 기준으로 우선순위 큐 생성

        pq.add(new Edge(1,0)); // 시작 지점 

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

            if(visit[cur.w])
                continue;

            visit[cur.w] = true; // 방문 처리
            result += cur.cost; // 총 가중치 합 갱신

            for(Edge e : graph[cur.w])
            {
                if(!visit[e.w])
                {
                    pq.add(e); // 연결된 간선의 정보 추가
                }
            }
        }

        System.out.println(result);
    }
}
class Edge
{
    int w;
    int cost;

    Edge(int w,int cost)
    {
        this.w = w;
        this.cost = cost;
    }
}