제육's 휘발성 코딩
Published 2022. 2. 25. 22:51
[JAVA] - 최소 신장 트리 🔷 Java/Basic
반응형

서로소 집합 (Disjoint-set)

  • 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들 (교집합 X)
  • 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분 (대표자)
  • 연결 리스트 또는 트리로 서로소 집합을 표현
Make-Set(x)
  p[x] <- x
  • Make-Set(x) : 최소 단위 집합 생성
Find-Set(x)
  IF x == p[x] : Return x
  ELSE : Return Find_Set(p[x])
  • Find-Set(x) : x가 속한 집합 찾기 (대표자)
Union(x,y)
  IF Find_Set(y) == Find_Set(x) Return;
  p[Find_Set(y)] <- Find_Set(x)
  • Union(x,y) : x가 속한 집합, y가 속한 집합 합쳐서 하나의 집합으로 만듦 (서로소 집합 유지)

연결 리스트

  • 연결리스트의 맨 앞의 원소를 대표 원소로 삼고 하나의 연결리스트로 관리
  • 각 원소는 대표원소를 가리키는 링크를 갖는다.

트리

  • 같은 집합의 원소들을 하나의 트리로 표현
  • 자식 노드가 부모를 가리키며, 루트 노드가 대표자
  • 자식들이 부모를 기억하고 있으며 집합끼리 합쳐질때 루트노드 끼리 연결 된다.

Path Compression

  • Find-Set 연산에서 특정 노드에서 루트까지의 경로를 찾아가면서 노드의 부모 정보를 갱신
  • 연산의 효율성은 증가했지만, 모든 경우에 해결이 되지는 않는다.

Rank

  • 패스 압축을 한 순간 효율성이 증가하지만, 한 방향에서 계속 노드가 붙는 경우를 방지하기 위해 랭크 관리를 한다.
  • 하지만 랭크 관리를 하기 위해선 완전 탐색을 해야되기 때문에 효율적이진 않다.
import java.util.Arrays;

public class DisjointSetTest {
    static int N;
    static int[] parents;

    // 단위 집합 생성
    public static void makeSet() {
        parents = new int[N];
        // 자신의 부모노드를 자신의 값으로 세팅
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }

    // a의 집합 찾기 : a의 대표자 찾기
    public static int findSet(int a) {
        // 내가 루트이면 리턴
        if (a == parents[a]) return a;
        return parents[a] = findSet(parents[a]); // path compression
    }

    // a,b 두 집합 합치기
    public static boolean union(int a, int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);
        if(aRoot == bRoot) return false;
        parents[bRoot] = aRoot;
        return true;
    }

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

        System.out.println("============find==============");
        System.out.println(findSet(4));
        System.out.println(Arrays.toString(parents));
        System.out.println(findSet(3));
        System.out.println(Arrays.toString(parents));
        System.out.println(findSet(2));
        System.out.println(Arrays.toString(parents));
        System.out.println(findSet(0));
        System.out.println(Arrays.toString(parents));
        System.out.println(findSet(1));
        System.out.println(Arrays.toString(parents));
    }
}

최소 신장 트리 (MST)

  • 그래프에서 최소 비용 문제
    • 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
    • 두 정점 사이의 최소 비용의 경로 찾기
  • 신장 트리
    • n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
  • 최소 신장 트리 (Minimum Spanning Tree)
    • 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

크루스칼 알고리즘

  • 간선을 하나씩 선택해서 MST를 찾는 알고리즘 - 간선 리스트
  1. 최초, 모든 간선을 가중치에 따라 오름차순 정렬
  2. 가중치가 낮은 간선 부터 선택하면서 트리 증가 - 사이클이 존재하면 선택하지 않고 다음으로 가중치가 낮은 간선 선택
  3. n-1 개의 간선이 될 때 까지 2를 반복
/*
TestCase

5 10
0 1 5
0 2 10
0 3 8
0 4 7
1 2 5
1 3 3
1 4 6
2 3 1
2 4 3
3 4 1
==>10

7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
==>175
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class MST1_KruskalTest {
    static class Edge implements Comparable<Edge>{
        int from, to, weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

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

    static int N;
    static int[] parents;
    static Edge[] edgeList;

    // 단위 집합 생성
    public static void makeSet() {
        parents = new int[N];
        // 자신의 부모노드를 자신의 값으로 세팅
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }

    // a의 집합 찾기 : a의 대표자 찾기
    public static int findSet(int a) {
        // 내가 루트이면 리턴
        if (a == parents[a]) return a;
        return parents[a] = findSet(parents[a]); // path compression
    }

    // a,b 두 집합 합치기
    public static boolean union(int a, int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);
        if(aRoot == bRoot) return false;
        parents[bRoot] = aRoot;
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        edgeList = new Edge[E];

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            edgeList[i] = new Edge(from,to,weight);
        }
        Arrays.sort(edgeList);
        makeSet();

        int result = 0, cnt = 0;

        for (Edge edge : edgeList) {
            if (union(edge.from, edge.to))  {
                result += edge.weight;
                if(++cnt == N-1) break;
            }
        }
        System.out.println(result);
        for (Edge x : edgeList) {
            System.out.println(x.from +" " + x.to +" " +x.weight);
        }
    }
}

프림 알고리즘

image

  • 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 - 정점 중심 해결
  • 한 정점을 선택한 후 그 정점을 선택했을 때 가능한 다른 정점과의 간선 비용을 최소로 업데이트
  • 어느 정점에서 시작해도 결과는 같다.
  • 다익스트라 방식과 비슷한 방식
  1. 임의 정점을 하나 선택해서 시작 (신장트리 구성에 포함시킬 최소 비용 정점 선택)
  2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점(아직 신장 트리에 구성이 되지 않은 정점)을 선택
  3. 모든 정점이 선택될 때 까지 1, 2 과정을 반복

2번을 진행하는 이유는 최소 비용만 계속 갱신하면 중복 계산을 제거할 수 있기 때문이다. 모든 정점을 새로 비교하는 것이 아닌 최소 비용값(min)과 비교할 정점의 비용만 비교

  • 서로소인 2개의 집합 정보를 유지
    • 트리 정점들 - MST를 만들기 위해 선택된 정점들
    • 비트리 정점들 - 선택되지 않은 정점들
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
5
0 5 10 8 7
5 0 5 3 6
10 5 0 1 3
8 3 1 0 1
7 6 3 1 0
==>10

7
0 32 31 0 0 60 51
32 0 21 0 0 0 0
31 21 0 0 46 0 25
0 0 0 0 34 18 0
0 0 46 34 0 40 51
60 0 0 18 40 0 0
51 0 25 0 51 0 0
==>175
 */
public class MST2_PrimTest {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        int[][] adjMatrix = new int[N][N];
        int[] minEdge = new int[N]; // 타 정점에서 자신으로의 간선 비용 중 최소비용
        boolean[] visited = new boolean[N]; // 신장 트리에 선택된 여부
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                adjMatrix[i][j] = Integer.parseInt(st.nextToken());
            }
            minEdge[i] = Integer.MAX_VALUE;
        }

        int result = 0;
        minEdge[0] = 0;

        // N개의 정점을 모두 연결
        for (int c = 0; c < N; c++) {
            // 신장트리에 연결되지 않은 정점 중 가장 유리한 비용의 정점을 선택
            int min = Integer.MAX_VALUE;
            int minVertex = 0;

            for (int i = 0; i < N; i++) {
                if(!visited[i] && min > minEdge[i]) {
                    min = minEdge[i];
                    minVertex = i;
                }
            }

            // 선택된 정점을 신장트리에 포함시킴
            visited[minVertex] = true;
            result += min;

            // 선택된 정점 기준으로 신장트리에 포함되지 않은 다른 정점으로의 간선 비용을 따져보고 최솟값 갱신
            for (int i = 0; i < N; i++) {
                if (!visited[i] && adjMatrix[minVertex][i] != 0 && minEdge[i] > adjMatrix[minVertex][i]) {
                    minEdge[i] = adjMatrix[minVertex][i];
                }
            }
        }
        System.out.println(result);
    }
}

Priority Queue

  • 프림 알고리즘에서 1단계를 pq로 최솟값을 구하고, 2단계에서 pq에 최솟값을 넣어주는 방식으로 구현할 수 있다.

최단 경로 알고리즘

  • 가중치가 있는 그래프에서 두 정점 사이의 경로 중에서 가중치의 합이 최소인 경로 (가중치가 없다면 BFS가 유리)
  • 다익스트라(dijkstra) : 음의 가중치를 허용하지 않음
  • 벨만-포드(bellman-ford) : 음의 가중치 허용
  • 플로이드-워샬(floyd-warshall) : 모든 정점들에 대한 최단 경로

다익스트라 알고리즘

  • 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사
  • 출발지에서 각 정점까지 오는 최소 비용을 계산

image

  • 1 단계 : 각 정점으로 오기까지의 최소 비용 계산을 위한 배열 최댓값으로 초기화
  • 2 단계 : 시작 정점 A를 0으로 변경 후 갈 수 있는 정점의 비용 변경 , A 정점 방문 처리
  • 3 단계 : 정점 B가 최소 비용이므로 B를 시작으로 비용 변경 , B 정점 방문 처리
    • C : B->C : 5 , d[C] : 2 이므로 변경 X
    • D : B->C : 7 , d[D] : 5 이므로 변경 X
    • E : B->C : 11, d[E] : 9 이므로 변경 X
  • 4 단계 : 정점 C가 최소 비용이므로 C를 시작으로 비용 변경 , C 정점 방문 처리
    • E : C->E : 8, d[E] : 9 이므로 변경
  • 모든 정점 별 탐색을 마친 후 목적지인 E에 해당 하는 최소 비용인 d[E]가 최단 거리가 된다.
package day0224;

/*
5
0 2 2 5 9
2 0 3 4 8
2 3 0 7 6
5 4 7 0 5
9 8 6 5 0

output==> 8


6
0 3 5 0 0 0
0 0 2 6 0 0
0 1 0 4 6 0
0 0 0 0 2 3
3 0 0 0 0 6
0 0 0 0 0 0

output==> 12


10
0 4 6 0 0 0 0 0 0 0
0 0 0 9 8 0 0 0 0 0
0 3 0 0 2 3 0 0 0 0
0 0 0 0 0 0 6 0 0 0
0 0 0 2 0 1 3 7 0 0
0 0 0 0 0 0 0 4 8 0
0 0 0 0 0 0 0 0 0 13
0 0 0 0 0 0 0 0 0 9
0 0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0 0


output ==> 21

 */
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class DijkstraTest1 {
    public static void main(String[] args) throws IOException {
       // System.setIn(new FileInputStream("dijkstra_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int V = Integer.parseInt(br.readLine());
        int[][] adjMatrix = new int[V][V];
        int start = 0;
        StringTokenizer st = null;
        for (int i = 0; i < V; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < V; j++) {
                adjMatrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 출발지에서 자신으로 오는 최소 비용
        int[] distance = new int[V];

        // 최소비용 확정 여부
        boolean[] visited = new boolean[V];

        Arrays.fill(distance, Integer.MAX_VALUE);

        // 시작 정점 0으로 시작
        distance[start] = 0;

        for (int i = 0; i < V; i++) {
            // 1 단계 : 최소 비용이 확정되지 않은 정점 중 최소 비용의 정점 선택
            int min = Integer.MAX_VALUE, current = 0;
            for (int j = 0; j < V; j++) {
                if(!visited[j] && min > distance[j]) {
                    min = distance[j];
                    current = j;
                }
            }

            visited[current] = true;

            // 2 단계 : 선택된 정점을 경유지로 하여 아직 최소 비용이 확정되지 않은 다른 정점의 최소 비용을 고려
            for (int j = 0; j < V; j++) {
                if (!visited[j] && adjMatrix[current][j] != 0 && distance[j] > distance[current] + adjMatrix[current][j]) {
                    distance[j] = distance[current] + adjMatrix[current][j];
                }
            }
        }
        System.out.println(distance[V-1]);
    }
}
반응형
저작자표시
profile

제육's 휘발성 코딩

@sasca37

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요! 맞구독은 언제나 환영입니다^^

검색 태그

자바스크립트
javascript
자료구조
JPA
자바
AOP
jpql
프로그래머스
이펙티브자바
스프링

티스토리툴바