백준 1922번 : 네트워크 연결 java

이 문제는 최소 비용 신장 트리를 만드는 방법입니다.

최소 비용 신장 트리를 만드는 방법에는 프림 알고리즘과 크루스칼 알고리즘이 있습니다.

저는 이 문제를 풀 때 프림 알고리즘을 선택해서 풀었습니다.

크루스칼 알고리즘을 이용하여 최소 비용 신장 트리를 만드는 방법은 아래의 링크에 있습니다.

백준 1197번 : 최소 스패닝 트리 java

프림 알고리즘이란 임의의 정점을 기준으로 그 정점의 경로와 연결된 다른 정점들의 경로 중에서 가장 가중치가 적은
경로를 선택하며 최소 비용 신장 트리를 만드는 방법입니다.

위의 예제 1번을 통해서 이에 대해서 설명드리겠습니다.

예제 1번을 그림으로 나타내면 다음과 같습니다.

이제 1번 정점을 선택하여 프림 알고리즘을 실행해 보겠습니다.

선택한 경로와 정점은 빨간색으로 나타내겠습니다.

1과 연결된 간선 중에서 가장 가중치가 낮은 건 3으로 가는 4입니다.

따라서 3번 정점으로 가는 간선을 선택해줍니다.

그다음 1과 3 정점 중에서 가장 가중치가 낮은 간선은 3에서 2로 가는 정점입니다.

이 간선을 선택해주고 2번 정점도 포함시켜줍니다.

그다음으로 가중치가 낮은 간선은 1에서 2로 가는 간선이지만 이미 1에서 2로 갈 수 있기 때문에 이 간선은
선택할 수 없습니다.

따라서 3에서 4로 가는 4의 가중치를 가진 간선을 선택합니다.

그 다음으로 4에서 5로 가는 간선이 가중치가 제일 낮으니 선택해줍니다.

마지막으로 6번 정점과 연결된 가장 낮은 가중치를 가진 간선을 선택해줍니다.

이제 다른 간선들은 필요 없으니 선택되지 않은 간선들은 모두 지워주겠습니다.

위의 트리가 프림 알고리즘으로 만들어진 최소 비용 신장 트리입니다.

이 간선들의 가중치를 모두 합하면 23이 됩니다.

이제 이 알고리즘을 구현한 코드를 보여드리겠습니다.

---

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

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

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        List<List<Node>> ll = new LinkedList<>();
        boolean[] visited = new boolean[N+1];

        for(int i = 0; i<N+1; i++)
            ll.add(new LinkedList<>());

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

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());

            ll.get(A).add(new Node(B, val));
            ll.get(B).add(new Node(A, val));
        }

        Queue<Node> q = new PriorityQueue<>();
        for(int i = 0; i<ll.get(1).size(); i++)
            q.offer(ll.get(1).get(i));
        visited[1] = true;
        int sum = 0;

        while(!q.isEmpty()){
            Node a = q.poll();

            if(visited[a.B])
                continue;

            visited[a.B] = true;
            sum += a.val;
            for(int i = 0; i<ll.get(a.B).size(); i++)
                q.offer(ll.get(a.B).get(i));
        }

        System.out.println(sum);
    }
}
class Node implements Comparable<Node>{
    int B, val;

    Node(int B, int val){
        this.B = B;
        this.val = val;
    }

    @Override
    public int compareTo(Node a){
        return val - a.val;
    }
}

우선순위 큐를 이용하여 가중치가 낮은 순으로 간선들을 저장하게 만들었습니다.