[Algorithm/Java] 알고리즘 자바 원더랜드 프림 (코딩테스트, Greedy Algorithm, 탐욕 알고리즘, Priority Queue, 최소 스패닝 트리, 최소 신장 트리, Prim)

---

1. 문제 설명

• 설명
  원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
  원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 아래의 그림은 그 한 예를 설명하는 그림이다.
  

  

  
  위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.
• 입력
  첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.
  다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.
  이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.
• 출력
  모든 도시를 연결하면서 드는 최소비용을 출력한다.

 

 

 

 

2. 문제 코드 및 풀이 설명

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

// 그래프를 표현하기 위한 클래스
class Edge3 implements Comparable<Edge3> {
  public int vex;
  public int cost;

  Edge3(int vex, int cost) {
    this.vex = vex;
    this.cost = cost;
  }

  @Override
  public int compareTo(Edge3 ob) {
    return this.cost - ob.cost;
  }
}

public class WonderlandPrim {
  public static void main(String[] args) {
    Scanner kb = new Scanner(System.in);
    int n = kb.nextInt();
    int m = kb.nextInt();
    ArrayList<ArrayList<Edge3>> graph = new ArrayList<ArrayList<Edge3>>();
    for (int i = 0; i <= n; i++) {
      graph.add(new ArrayList<Edge3>());
    }
    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 Edge3(b, c));
      graph.get(b).add(new Edge3(a, c));
    }
    int answer = 0;

    // 간선의 길이가 작은 것을 뽑기위한 우선순위 큐
    PriorityQueue<Edge3> pQ = new PriorityQueue<>();
    pQ.offer(new Edge3(1, 0)); // 간선하나를 넣어주고 시작

    while (!pQ.isEmpty()) {
      Edge3 tmp = pQ.poll(); // 길이가 작은 정점 하나를 꺼내고
      int ev = tmp.vex;
      // 정점을 연결
      if (ch[ev] == 0) { // 가려하는 정점이 연결되어있지 않을 때만 실행
        ch[ev] = 1; // 체크해주고
        answer += tmp.cost; // 간선의 길이를 추가
        for (Edge3 ob : graph.get(ev)) { // 도달한 뒤 그 정점에 연결된 다른 정점을 큐에 저장
          // 이전에 확인한 현재 정점에 도달하기 위한 간선을 제외하고 모두 저장
          if (ch[ob.vex] == 0) pQ.offer(new Edge3(ob.vex, ob.cost));
        }
      }
    }
    System.out.println(answer);
  }
}

 

 

3. 출력 예시

입력
9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

출력
196

 

 

 

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의