백준 No.5972 택배 배송 - JAVA

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N개의 헛간과, 소들의 길인 M개의 양방향 길이 그려져 있고, 각각의 길은 C마리의 소들이 있습니다. 소들의 깉은 두 개의 떨어진 헛간인 A와 B를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

      [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3  

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

 

풀이

- dist 배열을 만들고 해당 배열에 인덱스를 노드로 보고 각 최단 경로를 하나씩 넣는다.

- 값을 입력받을 때 양방향이므로 

graph.get(A).add(new Node(B,C));

graph.get(B).add(new Node(A,B));

이런식으로 해주고 다익스트라 메소드 실행하면 정답이다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int dist[];
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int N,M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =new StringTokenizer(br.readLine() );
        N = Integer.parseInt(st.nextToken());   //헛간 그래프
        M = Integer.parseInt(st.nextToken());   //간선

        dist = new int[N+1];

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

        for(int i =0;i<M;i++){
            st= new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            graph.get(A).add(new Node(B,C));
            graph.get(B).add(new Node(A,C));
        }

        Arrays.fill(dist,Integer.MAX_VALUE);

        dijst();
        System.out.println(dist[N]);
    }

    static void dijst(){
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        queue.add(new Node(1,0));
        dist[1] = 0;

        while (!queue.isEmpty()){
              Node now = queue.poll();

              for(Node next : graph.get(now.v)){
                  if(dist[next.v] > dist[now.v]+next.cost){
                      dist[next.v] =dist[now.v]+next.cost;
                      queue.add(new Node(next.v,dist[next.v]));
                  }
              }
        }
    }

    static class Node{
        int v;
        int cost;

        public Node(int v,int cost){
                this.v = v;
                this.cost = cost;
        }
    }
}