최소비용구하기-다익스트라알고리즘(백준 1916번)

이전에 게시했던 최단 거리문제가 코드가 동일하다. 단지 출력하는 부분의 코드만 살짝 수정해주면된다. 즉, 최소비용문제 또한 다익스트라 알고리즘으로 풀수 있다.

---

백준-1916번 최소비용 구하기

---

package graph;
 
import java.util.ArrayList;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;

class AdjVertex2 implements Comparable<AdjVertex2> {
    int adjVertex;
    int weight;
    public AdjVertex2(int adjVertex,int weight) {
        // TODO Auto-generated constructor stub
        this.adjVertex=adjVertex;
        this.weight=weight;
    }
    @Override
    public int compareTo(AdjVertex2 o) {
        // TODO Auto-generated method stub
        if(this.weight>o.getWeight()) return 1;
        else if(this.weight==o.getWeight()) return 0;
        else return -1;
    }
    public int getAdjVertex() {
        return adjVertex;
    }
    public void setAdjVertex(int adjVertex) {
        this.adjVertex = adjVertex;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
}
public class Baekjun1916UpdateCode {
    static ArrayList<AdjVertex2>[] vertexList;
    static int[] distance;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        PriorityQueue<AdjVertex2> pq=new PriorityQueue<AdjVertex2>();
        
        int V=sc.nextInt();
        int E=sc.nextInt();
        
        vertexList=new ArrayList[V+1];
        distance=new int[V+1];
        for(int i=1;i<V+1;i++) {
            vertexList[i]=new ArrayList<AdjVertex2>();
            distance[i]=Integer.MAX_VALUE;
        }
        
        for(int i=0;i<E;i++) {
            int u=sc.nextInt();
            int v=sc.nextInt();
            int w=sc.nextInt();
            AdjVertex2 adVertex=new AdjVertex2(v,w);
            vertexList[u].add(adVertex);
        }
        int K=sc.nextInt();
        int M=sc.nextInt();
        distance[K]=0;
        pq.offer(new AdjVertex2(K,distance[K]));
        while(!pq.isEmpty()) {
            AdjVertex2 vertexInfo=pq.poll();
            int index=vertexInfo.getAdjVertex();
            int weight=vertexInfo.getWeight();
            Iterator<AdjVertex2> it=vertexList[index].iterator();
            while(it.hasNext()) {
                AdjVertex2 adVertex=it.next();
                int index1=adVertex.getAdjVertex();
                int weight1=adVertex.getWeight();
                    
                if(distance[index1]>distance[index]+weight1) {
                distance[index1]=distance[index]+weight1;
                pq.offer(adVertex);
                }
            }
        }
        System.out.println(distance[M]);
    }
}
 

출발도시에서 도착도시까지의 최소비용을 구하는 것이므로 출력부분을 도착도시의 거리를 출력해주면된다. 왜냐하면 다익스트라 알고리즘은 시작정점으로부터 모든 정점까지의 최소비용들이 모두 distance배열에 들어가기때문에 단순히 앞의 최단경로 문제 코드에서 출력부분만 수정해주면 된다. 다익스트라 알고리즘 구동방식은 최단거리문제 설명에 그림으로 설명되어있다.