[MST] BOJ 1197번: 최소 스패닝 트리

2023. 9. 22. 22:12·Computer Science/Algorithms

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

 

1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이

www.acmicpc.net

 

 

package Data_Structure.union_find;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Edge implements Comparable<Edge> {
    int v1;
    int v2;
    int cost;

    public Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        if (this.cost < o.cost) {
            return -1;
        } else if (this.cost == o.cost) {
            return 0;
        } else {
            return 1;
        }
    }
}
public class Main {

    private static boolean union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x==y) return false;

        if (x>y) parent[x] = y;
        else parent[y] = x;

        return true;
    }

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

    static int[] parent;
    static List<Edge> edgeList;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int e = sc.nextInt();

        edgeList = new ArrayList<>();

        for (int i=0; i<e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            edgeList.add(new Edge(a,b,c));
        }
        parent = new int[v+1];
        for (int i=1; i<=v; i++) {
            parent[i] = i;
        }

        Collections.sort(edgeList);

        int sum = 0;
        for (int i=0; i<edgeList.size(); i++) {
            Edge edge = edgeList.get(i);
            if (union(edge.v1, edge.v2)) {
                sum += edge.cost;
            }
        }
        System.out.println(sum);
    }
}
'Computer Science/Algorithms' 카테고리의 다른 글
  • [트리] 트리의 지름 구하기
  • [링크드 리스트] 링크드 리스트 뒤집기
  • [위상 정렬] 문제로 이해하는 topology sort
  • [최단 경로] 문제로 이해하는 dijkstra algorithm
kimdozzi
kimdozzi
끝까지 포기하지 않으면, 내가 다 이겨!
  • kimdozzi
    도브로
    kimdozzi
  • 전체
    오늘
    어제
    • 분류 전체보기 (132)
      • Problem Solving (49)
        • Baekjoon (29)
        • Programmers (0)
        • LeetCode (17)
        • 삼성 유형 (2)
      • Computer Science (27)
        • Operating System (2)
        • Algorithms (13)
        • Network (6)
        • DataBase (6)
      • Backend (33)
        • JavaScript (0)
        • TypeScript (6)
        • Java (7)
        • Spring Boot (7)
        • Spring Security (6)
        • JPA (2)
        • Mybatis (1)
        • Junit5 (1)
        • Redis (3)
      • DevOps (14)
        • Git, Github (5)
        • docker (4)
        • AWS (3)
        • nginx (2)
      • etc (6)
        • IntelliJ (3)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
    • 티스토리
    • 설정
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    도커
    python
    타입스크립트
    오블완
    Bucket
    docker
    점 업데이트
    오프라인 쿼리
    imos법
    티스토리챌린지
    구간 업데이트
    온라인 쿼리
    백준
    알고리즘
    PrefixSum
    인덱서블 타입
    S3
    세그먼트 트리
    segment tree
    구간합
    인덱스 시그니처
    CORS
    누적합
    컨테이너
    TypeScript
    파이썬
    AWS
    docker image
    interface
    인터페이스
    삼성기출
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
kimdozzi
[MST] BOJ 1197번: 최소 스패닝 트리
상단으로

티스토리툴바