[BOJ] 1922번 : 네트워크 연결

🔗 문제 링크

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

🤔 문제

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

😮 문제 해결 방법

연결 비용을 최소로 하기위해 우선순위 큐를 이용하여 시작 정점(1번째 컴퓨터)를 넣어주고 인접한 컴퓨터를 연결할 때마다 가장 최소 비용이 드는 컴퓨터를 넣어준다.

이러한 작업을 반복하면 최소 비용으로 모든 컴퓨터를 연결이 가능하다. 이 방법은 최소 신장 트리 알고리즘 중 하나인 프림 알고리즘을 사용한 것이다.

📌 최소 신장 트리란?

✔ 그래프 내의 모든 정점을 포함하는 트리(Spanning Tree, 신장트리) 중 간선의 가중치 합이 최소인 트리를 말한다.

✔ 최소 신장 트리는 모든 정점들이 연결되야 하고 사이클이 있으면 안되는 특징이 있다.

✔ N개의 정점을 N-1개의 간선으로 연결할 수 있다.

✔ 최소 신장 트리 알고리즘은 프림 알고리즘과 크루스칼 알고리즘이 있다.

🚩 Java 코드

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_1922 {
    static class Computer implements Comparable<Computer> {
        private int node;
        private int distance;

        public Computer(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        @Override
        public int compareTo(Computer o) {
            return Integer.compare(this.distance, o.distance);
        }
    }

    private static int N,M;
    private static ArrayList<ArrayList<Computer>> graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        graph = new ArrayList<>();
        boolean[] visited = new boolean[N];

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

        //그래프 구성하기
        for(int j=0;j<M;j++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken())-1;
            int end = Integer.parseInt(st.nextToken())-1;
            int distance = Integer.parseInt(st.nextToken());

            graph.get(start).add(new Computer(end,distance));
            graph.get(end).add(new Computer(start,distance));
        }

        int dist = mst(visited);
        bw.write(String.valueOf(dist));
        br.close();
        bw.close();
    }

    private static int mst(boolean[] visited) {
        //우선순위 큐를 이용해 최소 거리를 가져와 사용
        PriorityQueue<Computer> pq = new PriorityQueue<>();
        pq.add(new Computer(0,0));
        int distance = 0;
        int count = 0;
        while(!pq.isEmpty()){
            Computer computer = pq.poll();
            if(visited[computer.node])
                continue;
            distance += computer.distance;
            visited[computer.node] = true;
            for(Computer cp : graph.get(computer.node)) {
                if (!visited[cp.node])
                    pq.add(cp);
            }
            count++;
            //컴퓨터의 개수만큼 큐를 돌린 경우 break
            if(count == N)
                break;
        }
        return distance;
    }
}

💬 코멘트

최소 신장 트리 알고리즘(크루스칼, 프림 알고리즘)을 공부하고 정리하는 시간을 가져야겠다.