백준 1922번 네트워크 연결 JAVA

링크텍스트

설명

풀이 흐름 설명

프로그래머스 Lv.3 섬 연결하기와 유사한 최소 스패닝 트리(MST) 문제로 판단하였다.
링크텍스트
따라서 크루스칼 알고리즘을 사용하여 해결하였다.

먼저 정점의 개수 n과 간선의 개수 m을 입력받았다.
이후 Union-Find를 사용하기 위해 parent 배열과 rank 배열을 초기화하였다.
간선 정보는 (시작 정점, 도착 정점, 비용) 형태로 저장하였고
비용 기준 오름차순 정렬을 위해 PriorityQueue를 사용하였다.

그 다음 우선순위 큐에서 간선을 하나씩 꺼내면서
두 정점이 서로 다른 집합에 속해 있다면 union을 수행하고
해당 간선의 비용을 총 비용에 더하도록 구현하였다.
모든 간선을 검사한 후 누적된 비용을 출력하였다.

고민과 해결 과정
처음에는 PriorityQueue에 간선을 넣어두고 다음과 같이 순회하였다.

for (Edge e : edges) {

논리적으로는 문제 없어 보였고 정렬도 되어 있을 것이라고 생각하였다.

그러나 PriorityQueue는 내부 배열이 정렬되어 있는 것이 아니라
poll()을 호출할 때마다 최소값이 보장되는 구조라는 점을 간과하였다.
즉 for-each로 순회하면 가중치 오름차순이 보장되지 않는다.
이로 인해 크루스칼의 핵심 조건인
“간선을 비용 기준으로 하나씩 선택한다”는 전제가 깨졌고
결과가 틀리게 나왔다.

이를 다음과 같이 수정하였다.

while (!edges.isEmpty()) {
    Edge e = edges.poll();

PriorityQueue는 반드시 poll()로 꺼내야 한다는 점을 다시 한 번 정리하게 되었다.

크루스칼 프림 정리

구분	크루스칼	프림
관점	간선 중심	정점 중심
시작점	필요 없음	아무 정점 1개 필요
자료구조	Edge 리스트	인접리스트 graph[]
간선 저장	한 번만	반드시 양방향
사이클 처리	Union-Find 필요	visited로 자동 방지
PQ 사용 방식	모든 간선 정렬	현재 연결된 간선만 관리
추가 변수	parent	visited[], count
그래프 형태	간선 리스트	인접 리스트
밀집 그래프	비효율적	더 유리
희소 그래프	매우 좋음	좋음

시간복잡도: O(ElogE), 공간복잡도: O(N+M)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {
        static int [] parent;
        static int [] rank;
        static int n,m;
        static PriorityQueue<Edge> edges = new PriorityQueue<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        parent = new int[n+1];
        rank = new int[n+1];

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

        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 c = Integer.parseInt(st.nextToken());

            edges.offer(new Edge(a,b,c));
        }

        int totalCost = 0;
        while(!edges.isEmpty()){
            Edge e = edges.poll();
            if(find(e.start)!=find(e.end)){
                union(e.start, e.end);
                totalCost += e.cost;
            }
        }

        System.out.println(totalCost);
    }

    static int find(int x){
        if(parent[x]!=x) return parent[x] = find(parent[x]);
        return x;
    }

    static void union(int a, int b){
        int ra = find(a), rb = find(b);

        if(ra==rb) return;

        if(rank[ra]<rank[rb]) parent[ra] = rb;
        else if(rank[ra]>rank[rb]) parent[rb] = ra;
        else{
            parent[rb] = ra;
            rank[ra]++;
        }

    }

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

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

        @Override
        public int compareTo(Edge e){
            return Integer.compare(this.cost, e.cost);
        }
    }
}

프림 코드

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

public class Main {
        static int n,m;
        static ArrayList<Node>[] graph;
        static boolean [] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        graph = new ArrayList[n+1];
        check = new boolean[n+1];
        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        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 c = Integer.parseInt(st.nextToken());

            graph[a].add(new Node(b, c));
            graph[b].add(new Node(a, c)); // 프림은 양방향 필요
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(1, 0));

        int count = 0;
        int totalCost = 0;

        while(!pq.isEmpty()){
            Node now = pq.poll();

            if(check[now.end]) continue;

            check[now.end] = true;
            totalCost+=now.cost;
            count++;

            if(count==n) break;

            for(Node next : graph[now.end]){
                if(!check[next.end]){
                    pq.offer(new Node(next.end,next.cost));
                    //pq.offer(next);
                }
            }
        }

        System.out.println(totalCost);
    }

    static class Node implements Comparable<Node>{
        int end, cost;

        Node(int end, int cost){
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node e){
            return Integer.compare(this.cost, e.cost);
        }
    }
}