BOJ_1922 : 네트워크 연결

👉 문제링크

---

---

🔸 문제 분석 🔸

• N개의 컴퓨터 사이 M개의 네트워크가 있다.
• 모든 컴퓨터를 연결할 수 있는 네트워크 최소 비용을 구한다.

🔸 문제 풀이 🔸

• 전형적인 MST 문제이다. 모든 노드를 한 번씩은 연결하며 최소 비용이 되도록 하기 때문이다.
• 여기서는 크루스칼(Kruskal) 알고리즘을 사용했다.

🔸 코드 🔸

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

public class Main {
    private static int[] parent;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        int N = Integer.parseInt(br.readLine()); // 컴퓨터 수
        int M = Integer.parseInt(br.readLine()); // 연결선 수
        parent = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        PriorityQueue<Network> pq = new PriorityQueue<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            pq.add(new Network(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // Kruskal
        int sum = 0;
        while (!pq.isEmpty()) {
            Network n = pq.poll();
            if (union(n.start, n.end)) {
                sum += n.cost;
            }
        }

        // Output
        bw.write(Integer.toString(sum));
        bw.flush();
    }

    private static int find(int a) {
        if (parent[a] == a) {
            return a;
        }
        return parent[a] = find(parent[a]);
    }

    private static boolean union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return false;
        }
        parent[a] = b;
        return true;
    }

    private static class Network implements Comparable<Network> {
        int start, end, cost;

        public Network(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Network o) {
            return this.cost - o.cost;
        }
    }
}

🔸 코드 해석 🔸

• 비용이 낮은 네트워크부터 하나씩 연결해보며, 서클이 생기지 않도록 union-find 알고리즘으로 같은 집합은 배제했다.
• 연결 될 때마다 그 네트워크 비용을 누적해 출력한다.

---

🔸 end 🔸

• 처음에 MST인 것은 알았지만, 알고리즘으로 다익스트라를 고르는 실수를 범했다.
  • 다익스트라는 반드시 MST가 나오는 것은 아니다.
  • 시작 노드를 1부터 n까지 한 번씩 돌아가면서 돌려서 가중치 최소값을 구하는 방식으로 예제는 통과했지만, 시간 초과가 났다.
• MST 관련 이론이 아직 부실한 것 같다. 공부가 더 필요하다.