문제 링크

성능 요약

메모리: 49980 KB, 시간: 592 ms

분류

최소 스패닝 트리, 그래프 이론

제출 일자

2025년 1월 3일 13:57:36

문제 설명

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

풀이

느낀점

• 최근에는 다익스트라를 활용하는 문제만 계속 풀다가 크루스칼을 오랜만에 풀어서 반가웠다.
• 오랜만에 해서 방법을 까먹었지만 원리를 생각하며 푸니 점차 기억이 났다.
• 크루스칼은 간선을 정렬해서 최소 길이 간선부터 방문하기 때문에 간선에 음수가 있어도 괜찮을 것 같았다.
• 첫번째 시도에서 틀렸습니다가 나왔는데 질문게시판을 보지않고 스스로 테스트 케이스를 만들어 확인한 점이 뿌듯했다.

설계 : 10분

• 입력받은 간선을 가중치 오름차순으로 정렬한 후 순회한다.
• 간선을 이루는 두 정점에 대해 findSet을 해서 동일한 트리에 연결되어있지 않은 경우 UnionSet 한다.
• 유니온을 할때 단순히 해당 간선의 부모 배열에서 가져와서 유니온 하지않고, 루트끼리 유니온을 해야 한다.

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 최소 스패닝 트리_1197
 * Date: 2025.01.03
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static int[] p;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int v = Integer.parseInt(input[0]);
        int e = Integer.parseInt(input[1]);

        Edge[] edges = new Edge[e];
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(left, right, w);
        }
        Arrays.sort(edges);

        p = new int[v+1];
        for (int i = 1; i <= v; i++) {
            p[i] = i;
        }

        int answer = 0;
        for (Edge edge : edges) {
            int left = findSet(edge.left);
            int right = findSet(edge.right);
            if (left != right) {
                answer += edge.w;
                p[left] = p[right];
            }
        }

        bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}

    private static int findSet(int num) {
        if (p[num] == num) return num;
        return p[num] = findSet(p[num]);
    }
}

class Edge implements Comparable<Edge> {
    int left;
    int right;
    int w;

    Edge() {}
    Edge(int left, int right, int w) {
        this.left = left;
        this.right = right;
        this.w = w;
    }

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