(Java) 백준 1197

Lee Yechan·2025년 4월 26일

Java boj ps 백준

문제

입력

출력

답안

풀이

알고리즘 문제 풀이

목록 보기

63/68

백준 1197

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	108803	38770	22723	37.736%

문제

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

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

입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

답안

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;

public class BOJ1197 {
    public static void main(String[] args) throws IOException {
		// 첫째 라인 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int vertexCount = Integer.parseInt(firstLine[0]);
        int edgeCount = Integer.parseInt(firstLine[1]);

		// 간선 정보 입력받기
		// Edge<시작 노드, 끝 노드, 가중치>	
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0; i < edgeCount; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            edges.add(new Edge(start, end, weight));
        }
        // 크루스칼 알고리즘에 사용하기 위해 가중치 오름차순 정렬한다.
        edges.sort(Comparator.comparingInt(edge -> edge.weight));

		// union-find 구조에 사용할 배열. 자신 노드가 속해 있는 그룹의 대표 노드의 번호가 저장된다.
        link = new int[vertexCount+1];
        for (int i = 1; i <= vertexCount; i++) {
            link[i] = i;
        }

		// 크루스칼 알고리즘
        long answer = 0;
        for (Edge edge: edges) {
		    // 사이클이 형성되지 않도록 union-find 이용
            if (find(edge.start) == find(edge.end)) {
                continue;
            }
            union(edge.start, edge.end);
            answer += edge.weight;
        }

        System.out.println(answer);
    }

    static class Edge {
        int start, end, weight;
        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    static int[] link;

    static void union(int nodeA, int nodeB) {
        int nodeAParent = find(nodeA);
        int nodeBParent = find(nodeB);
        if (nodeAParent != nodeBParent) {
            link[nodeAParent] = nodeBParent;
        }
    }

    static int find(int nodeNo) {
        if (link[nodeNo] == nodeNo) {
            return nodeNo;
        }
        return link[nodeNo] = find(link[nodeNo]);
    }
}