[알고리즘] 백준 1197 최소 스패닝 트리 -최소신장트리- 자바

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

백준 최소신장트리 단계별풀기의 두번째 문제입니다. ㅎㅎ

최소신장트리는 크르수칼 알고리즘을 사용하는 문제입니다.

 

https://ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

노드개수를 V, 변의 개수를 E라고 하면 O(ElogV)의 시간복잡도를 가집니다.

 

 

저는 풀기전 영상을 통해 개념을 먼저 복습하고 봤습니다.

www.youtube.com/watch?v=LQ3JHknGy8c

 

 

풀이방법은 다음과 같습니다.

 

1. 노드의 연결요소들을 리스트에 넣어 가중치 오름차순으로 정렬한다.

2. 연결요소 리스트들을 하나씩 꺼내어 유니온 파인드를 사용해 두 연결요소가 이미 연결이 되어있는지 확인합니다. (사이클 방지하기 위해)

3-1. 연결이 되어 있지 않다면 둘을 연결해주고 가중치를 답에 더해줍니다. 그리고 둘이 연결되어 있다는 것을 알려주기 위해 union을 해줍니다.

3-2 연결이 되어 있다면 둘을 연결해주지 않습니다. (이미 가중치가 적은게 연결되어 있으므로)

 

 

[풀이]

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

class Main {
    private static int[] parent;
    private static ArrayList<Edge> edgeList = new ArrayList<>();
    private static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt(); //노드
        int E = sc.nextInt(); //간선
        //parent 초기화
        parent = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            parent[i] = i;
        }
        //연결노드 초기화
        for (int e = 0; e < E; e++) {
            int A = sc.nextInt(); //연결노드
            int B = sc.nextInt(); //연결노드
            int C = sc.nextInt(); //가중치
            edgeList.add(new Edge(A, B, C));
        }
        Collections.sort(edgeList); //가중치 오름차순 정렬

        //최소신장트리 탐색
        for (int i = 0; i < edgeList.size(); i++) {
            Edge edge = edgeList.get(i);
            if (!isSameParent(edge.start, edge.end)) { //사이클이 발생하지 않은 경우 연결
                answer += edge.weight;
                union(edge.start, edge.end); //연결
            }
        }
        System.out.println(answer);
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y) parent[y] = x;
            else parent[x] = y;
        }
    }

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

    private static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }

    static class Edge implements Comparable<Edge> {
        int start;
        int end;
        int weight;

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

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

}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!