이번에 풀어본 문제는
백준 1922번 네트워크 연결 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Node
{
    int n,weight;

    public Node(int n, int weight)
    {
        this.n = n;
        this.weight = weight;
    }
}
public class Main {
    static List<List<Node>> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        map = new ArrayList<>();

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

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st;
        while(M-- > 0)
        {
            st = new StringTokenizer(br.readLine());
            int fst = Integer.parseInt(st.nextToken());
            int sec = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            map.get(fst).add(new Node(sec,w));
            map.get(sec).add(new Node(fst,w));
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.weight - o2.weight;
            }
        });

        pq.add(new Node(1,0));
        boolean [] visited = new boolean[N+1];
        int answer = 0,cnt = 0;
        while(!pq.isEmpty())
        {
            Node cur = pq.poll();
            if(visited[cur.n]) continue;
            visited[cur.n] = true;
            answer += cur.weight;
            cnt++;
            if(cnt == N) break;
            for(Node next : map.get(cur.n))
            {
                if(!visited[next.n]) pq.add(next);
            }
        }
        System.out.print(answer);
    }
}

📝 풀이

최소스패닝트리 입니다.
프림 알고리즘을 사용했고, 1번 컴퓨터를 시작점으로 하여 인접한 정점중 가중치가 작은 순서대로 (우선순위 큐 활용) 정점을 선택하여 트리를 완성했습니다.

📜 후기

최근 복습을 하고있어서 최소 스패닝트리 문제를 풀어보았습니다. 프림 알고리즘을 많이 활용해보지 못했었고, 입력조건에 따라 정점의 갯수가 간선보다 더 적을 것 같아서 정점으로 탐색을 진행하는 프림 알고리즘으로 풀어보았습니다.