백준 1647번 : 도시 분할 계획 java

이 문제는 최소 비용 신장 트리를 구성하는 문제입니다.

저는 프림 알고리즘을 이용하여 이 문제를 해결하였고 이 알고리즘에 대한 설명은 아래의 문제에 있습니다.

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

 

 

저는 프림 알고리즘을 이용하여 최소 비용 신장 트리를 만든 다음 간선 중에서 가장 큰 가중치를 가진 간선을 제거하여
마을을 2개로 나누었습니다.

바로 코드를 보여드리겠습니다.

---

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

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

        for(int i = 0; i<M; i++){
            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<>();
        q.offer(new Node(1, 0));
        int sum = 0;
        int max = Integer.MIN_VALUE;

        while(!q.isEmpty()){
            Node node = q.poll();
            if(visited[node.B])
                continue;

            visited[node.B] = true;
            sum += node.val;
            max = Math.max(max, node.val);

            for(int i = 0; i<ll.get(node.B).size(); i++){
                Node nextNode = ll.get(node.B).get(i);

                if(visited[nextNode.B])
                    continue;

                q.offer(new Node(nextNode.B, nextNode.val));
            }
        }

        System.out.println(sum - max);
    }
}
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;
    }
}

이와 같이 문제를 해결할 수 있습니다.