2022 02 14

2022-02-14

알고리즘 문제풀이 - 다익스트라 알고리즘 & Union Find

• 다익스트라 알고리즘
  • 모든 간선의 가중치가 0 이상일 경우 사용
  • PriorityQueue를 활용하여 O(nlogn)으로 쇼부가능

• Union Find
  • 그래프의 루트 원소를 계속 갱신해 나가기
  • 연결되어있다 => 루트를 하나로 만들기
  • 배열의 값으로 연결해두기

    static int[] unf;
    
    public static int Find(int v){
        if(v==unf[v]) return v;
        else return unf[v]=Find(unf[v]);
    }
    
    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb) unf[fa]=fb;
    }