트리 관련 개념 정리

트리 관련 개념 정리

신장트리와 최소비용 신장 트리

🟦신장트리 : n개 정점 무방향 그래프에서 간선 n-1개로 이루어진 부분 그래프

• 정점 n개, 간선 n-1개, 사이클X, 연결그래프(단절X)

🟦최소비용 신장 트리 : 무방향 가중치 그래프에서 신장 트리 구성 간선의 가중치 합이 최소인 그래프

• 1) 크루스칼 알고리즘
• (1) 가중치 높은 간선 제거하며 최소비용 만들기
• (2) 가중치 낮은 간선 삽입하며 최소비용 만들기
• 2) 프림 알고리즘
• (간선 정렬 X) 하나의 정점에서 시작하여 트리 확장해감
• 확장 정점들에 부속된 모든 간선들을 비교하며 가장 낮은 간선 연결 확장

---

🟪 최단 경로

🟦 최단 경로

• (신장트리가 아닌) 가중치 그래프에서 정점u와 정점 v를 잇는 경로 중 가중치 합이 최소인 경로
• 1) 다익스트라 최단 경로 알고리즘 | One-to-All
  • : 시작 정점 하나에서 다른 모든 정점까지의 최단 경로 구하기
  • (1) 시작 정점 에서 각 정점까지의 최단 경로 갖는 정점 u추가
  • (2) 추가된 u를 거쳐가는 경로 VS 기존 경로 비교 후 더 작은 값으로 업데이트
• 2) 플로이드 최단 경로 알고리즘 | All-to-All
  • : 모든 정점에서 다른 정점들 사이의 모든 최단 경로 구하기

---

9-5. 다익스트라 알고리즘 | 어려움

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/* 9=5. 다익스트라 알고리즘  */
class Edge implements Comparable<Edge>{
    public int vex;//정점
    public int cost;//가중치
    Edge(int vex, int cost){
        this.vex = vex;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge o) {
        // TODO Auto-generated method stub
        return this.cost-o.cost; //비용 오름차순
    }
}
public class Main1 {
    static int n, m;
    static ArrayList<ArrayList<Edge>> graph;
    static int[] dis;
    //솔루션 함수
    public void solution(int v) {
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.offer(new Edge(v, 0)); 
        dis[v]=0;//첫번째 방문 v는 0으로 처리 (: 시작정점)
        while(!pQ.isEmpty()) {
            Edge tmp = pQ.poll();//오르마순이므로 비용 최소가 poll됨
            int now = tmp.vex;//현재 정점
            int nowCost = tmp.cost;//현재 비용 
            if(nowCost > dis[now]) continue;

            //현재 뽑은 now정점과 연결도니 그래프 엣지들 하나씩 뽑아서 돈다.
            for(Edge ob : graph.get(now)) {
                //기존 거리 > 현재 비용 + 새 비용  
                if(dis[ob.vex] > nowCost + ob.cost) {
                    dis[ob.vex] = nowCost + ob.cost; //갱신
                    pQ.offer(new Edge(ob.vex, nowCost+ob.cost));//새로운 edge 담음
                }
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();

        graph = new ArrayList<ArrayList<Edge>>();
        for(int i=0; i<=n; i++) {
            graph.add(new ArrayList<Edge>());
        }
        dis = new int[n+1];
        //dis 배열을 모두 Max값으로 초기화 
        Arrays.fill(dis, Integer.MAX_VALUE);
        for(int i=0; i<m; i++) {
            int a= kb.nextInt();
            int b= kb.nextInt();
            int c = kb.nextInt();
            //출발점 a에 연결될 정점 b와 비용 c를 담는다.
            graph.get(a).add(new Edge(b, c));
        }

        T.solution(1);
        for(int i=2; i<=n; i++) {
            if(dis[i]!=Integer.MAX_VALUE) System.out.println(i+" : "+dis[i]);
            else {
                System.out.println(i+ "impossible");
            }
        }
    }    
}

9-6. 친구인가 | 서로소 집합| Union&Find

import java.util.Scanner;

/* 9-6. 친구인가 | 서로소 집합 Disjoint-Set: Union&Find 알고리즘 | */
public class Main2 {
    static int[] unf;
    //Find
    public static int Find(int v) {
        if(v==unf[v]) return v;
        else return unf[v] = Find(unf[v]);
    }
    //Union
    public static void Union(int a, int b) {
        int fa = Find(a);
        int fb = Find(b);

        if(fa!=fb) unf[fa] = fb;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb= new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();

        //unf 초기화
        unf = new int[n+1];
        for(int i=1; i<=n; i++) unf[i]= i;

        for(int i=1; i<=m; i++) {
            int a= kb.nextInt();
            int b= kb.nextInt();
            Union(a,b);
        }
        int a= kb.nextInt();
        int b= kb.nextInt();
        int fa = Find(a);
        int fb = Find(b);
        if(fa == fb) System.out.println("YES");
        else System.out.println("NO");    
    }
}

---

9-7. 원더랜드 | 크루스칼

/* 9-7. 원더랜드 (최소 스패팅 트리 - 크루스칼 : Union&Find 활용)  */

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

//간선 정보 담을 객체
class Edge implements Comparable<Edge>{
    public int v1;
    public int v2;
    public int cost;
    Edge(int v1, int v2, int cost){
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge o) {
        // TODO Auto-generated method stub
        return this.cost - o.cost; //비용 기준 오름차순 정렬 
    }
}

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

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        unf = new int[n+1];
        ArrayList<Edge> arr = new ArrayList<>();
        for(int i=1; i<=n; i++) unf[i]= i;
        for(int i=0; i<m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            int c = kb.nextInt();
            arr.add(new Edge(a,b,c));
        }
        //최소비용 누적할 용 
        int answer = 0;
        //비용 오름차순 정렬 
        Collections.sort(arr);
        for(Edge ob : arr) {
            int fv1 = Find(ob.v1); //v1의 집합 번호 받고
            int fv2 = Find(ob.v2); //v2의 집합 번호 받음 
            //두 번호 동일한 경우 같은 집합 소속이므로 추가해서는 안됨 
            if(fv1 != fv2) { //둘이 다른 집합 소소의 정점인 경우에 한해서 
                answer += ob.cost;
                Union(ob.v1, ob.v2);//둘을 한 집합으로 묶어서 추가하기 
            }
        }
        System.out.println(answer);
    }
}

---

9-8. 원더랜드 | 프림

/* 9-8. 원더랜드 | 프림으로 풀기 : PriorityQueue 사용하기 */
import java.util.*;
class Edge1 implements Comparable<Edge1>{
    public int vex;
    public int cost;
    Edge1(int vex, int cost) {
        this.vex = vex;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge1 ob){
        return this.cost-ob.cost;
    }
}
class Main3 {
    public static void main(String[] args){
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int m=kb.nextInt();
        ArrayList<ArrayList<Edge1>> graph = new ArrayList<ArrayList<Edge1>>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Edge1>());
        }
        int[] ch=new int[n+1];
        for(int i=0; i<m; i++){
            int a=kb.nextInt();
            int b=kb.nextInt();
            int c=kb.nextInt();
            graph.get(a).add(new Edge1(b, c));
            graph.get(b).add(new Edge1(a, c));
        }
        int answer=0;
        PriorityQueue<Edge1> pQ = new PriorityQueue<>();
        pQ.offer(new Edge1(1, 0));
        while(!pQ.isEmpty()){
            Edge1 tmp=pQ.poll();
            int ev=tmp.vex;
            if(ch[ev]==0){
                ch[ev]=1;
                answer+=tmp.cost;
                for(Edge1 ob : graph.get(ev)){
                    if(ch[ob.vex]==0) pQ.offer(new Edge1(ob.vex, ob.cost));
                }
            }
        }
        System.out.println(answer);
    }
}

---