자바 알고리즘 신장 트리(Spanning Tree) 알아보기

신장트리(Spanning Tree)

: 1)모든 정점을 포함하면서 2)간선의 가중치 합이 최소인 트리

모든 노드를 한번씩만 연결해서 트리형태로 만들고 싶음

최소의 비용으로 연결해주는 트리 

 

 n개의 정점으로 이루어진 무향 그래프에서 n개의 정점가 n-1개의 간선으로 이루어진 트리

최대 간선 n(n-1) / 2 

완전탐색시 너무 많은 수가 나옴 !!완전 탐색이 아닌 그리디 사용

: 그리디를 이용한 알고리즘

 

정렬이 가능하면 정렬이 최고!

정렬이 안된다면 탐색을 통해서!

 

크리스탈 알고리즘

: 간선 중심으로 최소 신장 트리를 구하는 알고리즘

 

1. 간선(Edge)의 비용을 이용해서 오름 차순으로 정렬

2. 비용이 적은 간선 부터 V-1개의 간선을 선택해 신장트리를 만든다

3. 간선을 선택할 때 cycle이 생기지 않는지 check

서로소 집합(Disjoint Set)로 사이클이 있으면 조인x 없으면 조인 => 트리는 사이클 x 확인이 필요

4. cycle이 생기지 않는 간선인 경우 선택하고 해당 비용을 누적

시간 복잡도

1. makeSet() => 시간 복잡도 O(v)
2. Edge정렬 => 시간 복잡도 O(ElogE)
3. union => 시간 복잡도 O(V+ 2*union(E,E)) => O(E)

O(v+ElogE+E) => O(ElogE)

 

//간선이 적으면 크리스탈 알고리즘 // 간선이 20% 정도 일때

//간선이 많으면 프림

서로소 집합(Disjoint Set)

- 서로소 관계

- 상호 배타 집합들은 서로 중복으로 포함된 원소가 없는 집합들이다. => 두 집합에 교집합이 없는 관계

- 집합에 속한 하나의 특정 멤버(대표자 root)를 통해 각 집합들을 구분한다.

출처: https://born2bedeveloper.tistory.com/29

 

모든 원소에 대해서 집합이 되지 않은 상태에서도 대표자를 뽑아야함

자기자신을 전부 대표자로 집합에 초기화 하는 단계

처음 서로소 집합을 만들 때는, 자기 자신을 집합의 부모라고 간주 :

 

1. makeset(x) : x를 원소로 갖는 최소 단위 집합 만들기 => x가 대표자(root)로 만들어 놓자

 

public class DisjointSet {
    static int N;
    // 원소의 부모를 담는 배열
    static int[] parents;

    /*
     * 모든 원소들에 대한 초기 값을 설정하는 함수
     * - 자기 자신을 root로 설정한다. 
     */
    public static void make() {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }

출처: https://born2bedeveloper.tistory.com/29

대표자를 찾는 방법:

2. findset(x) : x원소의 root를 찾는 함수

/*
 * 인자로 전달 받은 원소(v)의 root를 찾는 기능
 */
public static int find(int v) {
    // 부모가 나이면 끝, 아니라면 누군가가 부모 / 재귀 활용
    // root가 v인 경우, root를 찾았으니 종료
    if (parents[v] == v) {
        return v;
    }

    // 내가 루트가 아닌 부모가 있는 상황이므로 부모의 root를 또 찾으러 가기
    return find(parents[v]);
}

 

 

같은 집합이면 X 같은 집합(대표자)이 아니라면  union을 해준다:

3. union(x, y): x의 집합과 y의 집합을 합친다.

=> x의 root를 찾고 y의 root를 찾아 두 집합 중

하나의 집합의 root를 한 다른 하나의 집합의 원소로 만든다.

public static boolean union(int a, int b) {
    // 두 원소의 root를 먼저 찾아야 한다.
    int aRoot = find(a);
    int bRoot = find(b);

    // root가 동일할 때 union을 하면 cycle 발생
    if (aRoot == bRoot) {
        return false;
    }

    // a의 root를 b의 root에 연결
    parents[aRoot] = bRoot;

    return true;
}

 

* 실제 union 실행 값

public static void main(String[] args) {
    N = 6;
    parents = new int[N];
    make();
    System.out.println(Arrays.toString(parents)); 
    // [0, 1, 2, 3, 4, 5]

    union(1, 2);
    System.out.println(Arrays.toString(parents));
    // [0, 2, 2, 3, 4, 5]

    union(3, 4);
    System.out.println(Arrays.toString(parents));
    // [0, 2, 2, 4, 4, 5]

    union(5, 3);
    System.out.println(Arrays.toString(parents));
    // [0, 2, 2, 4, 4, 4]

    union(1, 5);
    System.out.println(Arrays.toString(parents));
    // [0, 2, 4, 4, 4, 4]

    System.out.println(find(1)); 
    // 4
    System.out.println(Arrays.toString(parents));
    // [0, 2, 4, 4, 4, 4]

    System.out.println(find(4)); 
    // 4
    System.out.println(Arrays.toString(parents));
    // [0, 2, 4, 4, 4, 4]
}

 

* 시간 복잡도

: 편향 트리 O(N)

문제점!! 편향 트리인 경우 시간 복잡도 O(N)=>path compression이 필요- 

 

- path compression

나의 부모를 루트로 바꾸어 버림

/*
 * 인자로 전달 받은 원소(v)의 root를 찾는 기능
 */
public static int find(int v) {
    // 부모가 나이면 끝, 아니라면 누군가가 부모 / 재귀 활용
    // root가 v인 경우, root를 찾았으니 종료
    if (parents[v] == v) {
        return v;
    }

    // 내가 루트가 아닌 부모가 있는 상황이므로 부모의 root를 또 찾으러 가기
    // 문제점: 편향 트리인 경우 시간 복잡도 O(N) => path compression이 필요

    // path compression: 찾아온 root를 나의 부모로 변경하기로 한 후 리턴
    parents[v] = find(parents[v]); // 루트를 찾음 / 나의 부모에 루트를 넣음
    return parents[v];
}

 

 

 

* 편향 트리 O(N)를 찾아온 root를 나의 부모로 변경하여 복잡도를 줄임

 

- 시간 복잡도

최악의 경우 2N(초기 make 횟수+pathCompression횟수) + 2(루트까지 find하는 횟수)*유니온횟수(E)

: E

 

프림 알고리즘

:정점 중심으로 최소 신장 트리를 구하는 알고리즘

1. 임의의 정점 선택
2. 그 정점과 인접한 정점을 잇는 간선 중 가중치가 가장 낮은 간선 선택
3. 그 간선이 연결하는 정점 선택, 모든 정점에 대해 2번 과정 반복

* 서로수 집합을 이용한 코딩테스트 (백준 16562 친구비)

package boj.bronze;

import java.util.Scanner;

public class Main_G5_16562_친구비 {

    static int N; // 학생 수
    static int M; // 친구 관계 수
    static int K; // 가지고 있는 돈
    static int[] parents; // Union-Find를 위한 부모 배열
    static int[] price;  // 각 학생의 친구비 가격

    // Union-Find 초기화: 각 학생을 자기 자신을 부모로 설정
    public static void make() {
        parents = new int[N];
        for (int i = 0; i < N; i++) {
            parents[i] = i; // 각 학생은 초기에는 자기 자신이 부모
        }
    }

    // Find 함수: 학생 v의 부모를 찾는 함수 (경로 압축 적용)
    public static int find(int v) {
        if (parents[v] == v) {
            return v; // 자기 자신이 부모이면, 그 값을 반환
        }
        return parents[v] = find(parents[v]); // 경로 압축: 부모를 찾은 후 바로 부모를 갱신
    }

    // Union 함수: 두 학생 a, b를 합치는 함수
    public static boolean union(int a, int b) {
        int aRoot = find(a); // 학생 a의 루트 부모를 찾음
        int bRoot = find(b); // 학생 b의 루트 부모를 찾음

        if (aRoot == bRoot) {
            return false; // 이미 같은 그룹에 속하면 합칠 필요 없음
        }

        // 가격이 더 적은 그룹이 부모가 되도록 합침
        if (price[aRoot] < price[bRoot]) {
            parents[bRoot] = aRoot; // aRoot가 부모
        } else {
            parents[aRoot] = bRoot; // bRoot가 부모
        }

        return true; // 성공적으로 두 그룹을 합침
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력
        N = sc.nextInt(); // 학생 수
        M = sc.nextInt(); // 친구 관계 수
        K = sc.nextInt(); // 가지고 있는 돈

        price = new int[N]; // 각 학생의 친구비 가격
        for (int i = 0; i < N; i++) {
            price[i] = sc.nextInt(); // 친구비 입력
        }

        make(); // Union-Find 초기화

        // M개의 친구 관계 처리
        for (int i = 0; i < M; i++) {
            int a = sc.nextInt() - 1; // 학생 a (0부터 시작하는 인덱스)
            int b = sc.nextInt() - 1; // 학생 b (0부터 시작하는 인덱스)
            union(a, b); // 두 학생을 합침
        }

        // 총 친구비 계산
        int totalCost = 0;
        for (int i = 0; i < N; i++) {
            if (find(i) == i) { // 학생이 루트 노드(그룹의 대표자)라면
                totalCost += price[i]; // 그 그룹의 친구비를 더함
            }
        }

        // 친구비가 K 이하이면 결과 출력, 아니면 "Oh no" 출력
        if (totalCost <= K) {
            System.out.println(totalCost); // 예산 내에 친구비가 들어가면 출력
        } else {
            System.out.println("Oh no"); // 예산을 초과하면 "Oh no" 출력
        }

        sc.close(); // 스캐너 종료
    }
}