원더랜드(최소 스패닝 트리 : 프림 , Priority Queue 활용)

in Algorithm on Java, Coding, Test

문제

설명

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

아래의 그림은 그 한 예를 설명하는 그림이다.

그림

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

입력

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.

출력

모든 도시를 연결하면서 드는 최소비용을 출려한다.

예시 입력 1

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

예시 출력 1

196

해결방법

89.png

  • 우선순위 큐를 통해서 해결하는 방법.
  • 큐는 항상 문제에 맞게 정렬한다. 여기서는 최소 비용 이므로, 비용 오름차순으로 정렬이 되게끔 한다.
  • 방향/무방향 그래프인지 확인 후에 로직에서 체크해주어야 한다.
  • 체크배열을 통해 선택한 정점인지 아닌지 체크 한다.

코드

import java.util.*;

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++) {
      // a 라는 정점에서 b 라는 정점에 가는 비용이 c 다.
      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);
  }
}

© 2024. Chiptune93 All rights reserved.