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

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

풀이

 

사용한 알고리즘 : 데익스트라(Dijkstra)

 

풀이전략

전형적인 데익스트라 알고리즘 문제이다.

 

우선순위 큐를 사용하지 않고, 각 노드에서 최단거리 노드를 구할 때 함수를 사용하면 시간초과가 발생했다.

 

따라서 우선순위 큐를 구현하고 거리에 따라 오름차순 정렬되도록 해야한다.

 

1. 시작 노드를 우선순위 큐에 먼저 inqueue하고 해당 노드를 방문처리, distance를 0으로 한다.

2. 우선순위 큐를 pop하고 해당 노드가 방문할 수 있는 노드들을 순회한다.

3. 순회 과정에서 목표로 하는 노드에 아직 방문한적 없으면서,

   현재 노드를 거쳐 해당 노드로 가는 거리가 해당 노드의 기존 distance보다 짧다면

   1) 목표 노드까지의 distance = '현재 노드까지의 distance' + '현재노드에서 해당 노드까지의 거리'로 수정

   2) 목표 노드의 방문 여부를 true로 변환

   3) 목표 노드의 번호와 목표 노드 distance를 Node 객체로 만들어 우선순위 큐에 inqueue 한다.

4. 2~3번 과정을 반복한 뒤, 목표로 했었던 노드의 distance 값을 출력한다.

 

제출코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

import static java.lang.String.valueOf;

public class Main {

    static LinkedList<LinkedList<Node>> graph;
    static int distance[];
    static boolean visited[];

    static class Node implements Comparable<Node>{
        int index;
        int distance;

        public Node(int index,int distance){
            this.index=index;
            this.distance=distance;
        }

        int getIndex(){
            return this.index;
        }
        int getDistance(){
            return this.distance;
        }

        @Override
        public int compareTo(Node node) {
            return this.distance>node.getDistance()?1:-1;  //오름차순
        }
    }

    static private void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start,0));
        distance[start]=0;

        while(!pq.isEmpty()){

            Node tempNode = pq.poll();
            int now=tempNode.getIndex();

            if(visited[now])  continue;

            visited[now]=true;
            for(Node node : graph.get(now)){
                if(!visited[node.getIndex()] && distance[node.getIndex()]>distance[now]+node.getDistance()){
                    distance[node.getIndex()]=distance[now]+node.getDistance();
                    pq.offer(new Node(node.getIndex(),distance[node.getIndex()]));
                }
            }
        }
    }

    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));
        StringTokenizer st;

        int N=Integer.parseInt(br.readLine());
        int M=Integer.parseInt(br.readLine());

        graph=new LinkedList<>();
        distance = new int[N+1];
        visited = new boolean[N+1];

        for(int i=0;i<=N;++i){
            graph.add(new LinkedList());
            distance[i]=987654321;
        }

        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            int sp=Integer.parseInt(st.nextToken());
            int objective=Integer.parseInt(st.nextToken());
            int distance=Integer.parseInt(st.nextToken());
            graph.get(sp).add(new Node(objective,distance));
        }

        st = new StringTokenizer(br.readLine());
        int start=Integer.parseInt(st.nextToken());
        int objective=Integer.parseInt(st.nextToken());
        dijkstra(start);

        bw.write(valueOf(distance[objective]));
        bw.flush();
        bw.close();
    }
}