최소 스패닝 트리(백준_1197)

2023. 1. 28. 15:44·BackEnd/알고리즘 공부

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

문제 설명

그래프가 주어졌을 때, 최소 신장 트리를 구현하고 가중치의 합을 구하는 문제이다.

 

 

문제에 대한 아이디어

최소 신장 트리를 구현하는 문제이다. 최소 신장 트리를 구하는 대표적인 알고리즘인 크루스칼 알고리즘으로 이 문제를 풀었다.

크루스칼 알고리리즘은 O(|E|log|E|)안에 최소신장트리를 만들 수 있다.
왜냐 하면 모든 edge를 탐색하는데 O(E) 시간이 걸리고 간선을 오름차순으로 정렬하는데 걸리는 시간은 O(|E|log|E|) 이기 때문이다.

 

1. 에지 리스트를 입력 받고 가중치 순으로 정렬한다.

2. 작은 에지부터 탐색하면서 크루스칼 알고리즘을 실행한다.

Node s와 Node e를 Union-find 연산 중 각각 find를 실행하고 cycle이 아니면 union을 실행한다. 

이렇게 총 노드-1번 반복한다. 왜냐하면 모든 노드가 연결하는 edge의 수는 노드 갯수 - 1 이기 때문이다.

만약 cycle이면 다음 인덱스로 바로 넘어간다.

 

구현

  • Edge
static class Edge implements Comparable<Edge>{
    private int a;
    private int b;
    private int c;
    public 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;
    }
}
  • Union
public static void union(int a, int b){
    a = find(a);
    b = find(b);
    if(a==b) return;
    else arr[b] = a;

}
  • Find
public static int find(int a){
    if(arr[a] == a) return a;
    else return arr[a] = find(arr[a]);
}
  • Main
static int arr[];
public static void main(String []args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(buf.readLine());
    int v = Integer.parseInt(st.nextToken());
    int e = Integer.parseInt(st.nextToken());
    //우선순위 큐 선언
    PriorityQueue<Edge> edges = new PriorityQueue<>();
    //정답 배열 만들기
    arr = new int[v+1];
    for(int i=1; i<v+1; ++i){
        arr[i] = i;
    }
    for(int i =0; i<e; ++i){
        st = new StringTokenizer(buf.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        edges.add(new Edge(a,b,c));
    }
    int useEdge =0;
    int result=0;
    //크루스칼 알고리즘 시작
    while(useEdge < v-1) {
       Edge edge = edges.poll();
       if (find(edge.a) != find(edge.b)) { //사이클이 아니면 union
             union(edge.a, edge.b);
             result += edge.c;
             useEdge++;
       }
    }
    System.out.println(result);
}

 

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_1197.java

 

GitHub - Heron-Woong/CodingTest_Practice

Contribute to Heron-Woong/CodingTest_Practice development by creating an account on GitHub.

github.com

 

'BackEnd > 알고리즘 공부' 카테고리의 다른 글

프로그래머스(베스트앨범)  (0) 2023.02.01
부분합(백준_1806)  (0) 2023.01.29
벨만-포드 알고리즘, 타임머신(백준_11657)  (1) 2023.01.26
위상정렬, 줄 세우기(백준_2252)  (0) 2023.01.24
유니온 파인드, 집합의 표현(백준_1717)  (0) 2023.01.22
'BackEnd/알고리즘 공부' 카테고리의 다른 글
  • 프로그래머스(베스트앨범)
  • 부분합(백준_1806)
  • 벨만-포드 알고리즘, 타임머신(백준_11657)
  • 위상정렬, 줄 세우기(백준_2252)
인프라 감자
인프라 감자
  • 인프라 감자
    삶은 인프라
    인프라 감자
  • 전체
    오늘
    어제
    • 분류 전체보기 (243)
      • 클라우드&인프라 (28)
        • 인프라 공부 (4)
        • AWS 구조와 서비스 (18)
        • 클라우드 공부 (4)
        • Terraform (2)
      • AWS Cloud School (13)
        • project (5)
        • Linux, Network (6)
        • Docker (2)
      • BackEnd (162)
        • JAVA 공부 (15)
        • 알고리즘 공부 (71)
        • MySQL 문제 풀기 (8)
        • 스프링 핵심 원리 - 기본편 (18)
        • 스프링 MVC 1편 (4)
        • 자바 ORM 표준 JPA 프로그래밍 (21)
        • 실전! 스프링 부트와 JPA 활용1 (8)
        • 실전! 스프링 부트와 JPA 활용2 (5)
        • 스프링 데이터 JPA (8)
        • Querydsl (4)
      • 혼자하는 프로젝트 (32)
        • 배달의 민족 클론코딩 (7)
        • 나만의 프로젝트 (10)
        • 스프링 부트로 구현한 웹 (15)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • Email
    • GitHub
  • 공지사항

  • 인기 글

  • 태그

    linux
    상속
    자바
    정렬
    프로그래머스
    디팬스 게임
    완전탐색
    dp
    유니온 파인드
    자동 배포
    중첩 선언
    다이나믹 프로그래밍
    스프링 핵심 원리-기본편
    조합
    백트래킹
    쿼드 압축
    네트워크 기본 용어
    이것이 자바다
    VPN
    querydsl
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
인프라 감자
최소 스패닝 트리(백준_1197)
상단으로

티스토리툴바