[문제풀이] 09-07. 원더 랜드(프림)

인프런, 자바(Java) 알고리즘 문제풀이

Greedy Alogorithm - 0907. 원더 랜드(크루스칼, 최소 신장 트리)

---

🗒️ 문제

---

🎈 나의 풀이

	private static List<List<Edge>> graph = new ArrayList<>();
    private static int[] ch;

    private static class Edge implements Comparable<Edge> {
        int vet, cost;

        public Edge(int vet, int cost) {
            this.vet = vet;
            this.cost = cost;
        }

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

    private static int solution() {
        int answer = 0;

        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.add(new Edge(1, 0));

        while(!pQ.isEmpty()) {
            Edge now = pQ.poll();

            if(ch[now.vet] == 0) {
                ch[now.vet] = 1;
                answer += now.cost;

                for(Edge e : graph.get(now.vet)) {
                    pQ.add(e);
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ch = new int[n+1];

        for(int i=0; i<=n; i++) graph.add(new ArrayList<>());

        for(int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            graph.get(a).add(new Edge(b, c));
            graph.get(b).add(new Edge(a, c));
        }

        System.out.println(solution());
    }

---

🖍️ 강의 풀이

  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 ob){
          return this.cost-ob.cost;
      }
  }
  class Main {
      public static void main(String[] args){
          Scanner kb = new Scanner(System.in);
          int n=kb.nextInt();
          int m=kb.nextInt();
          ArrayList<ArrayList<Edge>> graph = new ArrayList<ArrayList<Edge>>();
          for(int i=0; i<=n; i++){
              graph.add(new ArrayList<Edge>());
          }
          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 Edge(b, c));
              graph.get(b).add(new Edge(a, c));
          }
          int answer=0;
          PriorityQueue<Edge> pQ = new PriorityQueue<>();
          pQ.offer(new Edge(1, 0));
          while(!pQ.isEmpty()){
              Edge tmp=pQ.poll();
              int ev=tmp.vex;
              if(ch[ev]==0){
                  ch[ev]=1;
                  answer+=tmp.cost;
                  for(Edge ob : graph.get(ev)){
                      if(ch[ob.vex]==0) pQ.offer(new Edge(ob.vex, ob.cost));
                  }
              }
          }
          System.out.println(answer);
      }
  }

---

💬 짚어가기

해당 문제는 그래프의 최소 신장 트리를 구하는 문제이다.

▶︎ 신장 트리(Spanning Tree)
신장 트리는 그래프 내에 있는 모든 정점을 연결하며, 사이클이 없는 그래프를 의미한다.
$n$개 정점을 갖는 신장 트리의 간선 수는 $n-1$개이다.

▶︎ 최소 신장 트리(Minimun Spanning Tree)
최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리이다.
가중치는 거리, 비용, 시간 등 여러가지로 응용할 수 있다.

최소 신장 트리의 대표적인 알고리즘으로 프림(Prim)과 크루스칼(Kruskal)이 있다.
이번 풀이에서는 프림 알고리즘에 대해 알아보겠다.
( 크루스칼 알고리즘 풀이 ☛ 원더 랜드(크루스칼) )

🔎 프림(Prim) 알고리즘

1. 시작 정점 선택
   그래프에서 정점을 하나 선택하여 시작한다.

2. 최소 가중치 선택
   선택한 정점과 연결된 간선 중에서 가장 가중치가 작은 간선을 선택한다.
   이 간선으로 연결된 정점은 현재까지 선택된 정점들과 연결된 최소 가중치를 가진 간선이다.

3. 선택된 정점 집합에 추가
   선택된 간선으로 연결된 정점을 최소 신장 트리에 추가한다.

4. 반복
   최소 신장 트리에 포함된 정점들과 이어진 간선 중에서 가장 작은 가중치를 가진 간선을 선택하여
   해당 정점을 트리에 추가한다. 모든 정점이 최소 신장 트리에 포함될 때까지 반복한다.

프림 알고리즘은 시작 정점을 기준으로 가장 가까운 정점을 하나씩 추가해가면서 최소 신장 트리를
형성한다. 이를 통해 최종적으로 모든 정점이 연결된 최소 비용의 트리를 얻을 수 있다.

⏱️ 시간 복잡도 : $O(E$ $logV)$

간선의 수를 $E$(Edge), 노드의 수를 $V$(Vertex)라고 했을 때,

인접한 모든 간선 검사 : $O(E)$
트리와 인접한 간선 중 최소 가중치를 갖는 간선 선택 : $O(logE)$

$O(E$ $logE)$의 시간 복잡도를 갖는다.

이때, 중복 간선을 포함하지 않는 경우 간선의 개수는 항상 (노드의 개수)$^2$ 이하이다.
( 간선의 최대 개수 : 모든 노드가 연결 되어 있는 경우인 $V * (V-1)$ )

$logE$는 $log(V^2)$보다 작고, $log(V^2)$은 $2logV$와 같으므로, $O(logV)$로 표현할 수 있다.
따라서, 프림 알고리즘의 시간 복잡도를 $O(E$ $logV)$로 표현할 수 있다.

✔️ 코드 구현 살펴보기
위 과정을 작성된 코드와 비교하여 설명하면 다음과 같다. (강의 코드 참고)

Edge 클래스는 간선을 나타내며, vex은 정점을, cost는 가중치를
나타낸다.Comparable 인터페이스를 구현하여 가중치에 따라 정렬할 수 있도록 한다.

1. 그래프 생성
   입력 받은 간선 정보를 리스트 graph : ArrayList<ArrayList<Edge>>를 생성하여
   각 정점마다 연결된 간선들을 Edge 객체로 저장한다.

2. 간선 합치기
   특정 정점을 방문하여 인접한 정점을 PriorityQueue<Edge>에 추가한다.
   이후 가중치가 가장 작은 간선을 poll()하여 트리에 추가한다. (방문한 노드는 체크)

3. 결과 출력
   최소 비용 신장 트리의 가중치 합인 answer를 출력합니다.