백준 1647번: 도시 분할 계획(Java, 그래프, 최소신장트리)

☑️ 문제

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

✔️관련 알고리즘 개념

최소 신장 트리

☑️ 문제 분석

• 이 문제는 집(노드)를 길(에지)로 연결했을 때 비용(가중치)가 최소가 되도록 해야 하므로 최소 신장 트리의 개념을 이용하여 문제에 접근해야 한다.
• 문제에서는 모든 집을 연결하는 것이 아니라 집들을 길로 연결하여 두 개의 마을을 만들어야 한다. 만약 모든 집들을 연결하려면 N-1개의 에지를 사용하면 된다. 하지만 우리는 문제 요구 조건에 따라 두 개의 마을로 나눠야 하므로 N-2개의 에지만 사용하면 된다.
• 예시 입력 1을 분석해보자

  • 집의 개수는 7, 길의 개수는 12이고

  • 그 아래 12개의 줄에 집의 번호들과 비용이 작성되어 있다.

  • 최소 신장 트리를 사용하기 위해서는 우선순위 큐를 이용하여 비용이 낮은 순으로 정렬하고

  • 사이클 여부를 판단하기 위해 유니온 파인드를 수행해야 한다.

    7 12
    1 2 3
    1 3 2
    3 2 1
    2 5 2
    3 4 4
    7 3 6
    5 1 5
    1 6 2
    6 4 1
    6 5 3
    4 5 3
    6 7 4

☑️ 코드

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

public class Main {
    static int N, M; // 집의 개수, 길의 개수
    static int[] parent;
    static PriorityQueue<Edge> queue = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 베열 초기화
        parent = new int[N+1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        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 C = Integer.parseInt(st.nextToken());
            queue.add(new Edge(A, B, C));
        }

        int used_Edge = 0;
        int result = 0;
        while (used_Edge < N-2) {
            Edge poll = queue.poll();
            if(find(poll.A) != find(poll.B)) {
                union(poll.A, poll.B);
                used_Edge++;
                result += poll.C;
            }
        }

        System.out.println(result);

    }

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

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

        if(a != b) parent[b] = a;
    }

    static class Edge implements Comparable<Edge>{
        int A;
        int B;
        int C;

        Edge(int A, int B, int C) {
            this.A = A;
            this.B = B;
            this.C = C;
        }

        @Override
        public int compareTo(Edge o) {
            return this.C - o.C;
        }
    }

}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음