5972_택배 배송 *(거의 다 됨)

사용 알고리즘: 다익스트라

사용 언어: java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_bj_5972_택배배송 {
    static int n, m;
//    static int[][] map; //25억 노노해
    static ArrayList<Node>[] map;
    static boolean[] visited;
    static int[] dp; //1에서 N번 노드까지 가는 최소 가중치 저장

    public static void main(String[] args) throws IOException {
        input();

        init();
        dijkstra();

        System.out.println(dp[n]);
    }

    private static void init() { //입력 받은 값 사용 초기값 저장
        dp[1] = 0;
//        visited[1] = true;

//        for (Node second : map[1]) {
//            dp[second.to] = second.weight;
//        } --> 다익스트라 메소드에서, dp에 저장된 값보다 더 작은 값이 존재할 때만 q에 넣기 때문에 이 작업 뺴야 함
    }

    private static void dijkstra() {
        Queue<Node> q = new PriorityQueue<>(); //제일 가중치가 작은 애부터 찾아감
        q.offer(new Node(1, 0));

        while (!q.isEmpty()) {
            Node curNode = q.poll();

            if(visited[curNode.to]) continue;
            else visited[curNode.to] = true;

            for (Node nextNode : map[curNode.to]) {
                if(dp[curNode.to] + nextNode.weight < dp[nextNode.to]) {
                    dp[nextNode.to] = dp[curNode.to] + nextNode.weight;
                    q.offer(new Node(nextNode.to, dp[nextNode.to]));
                }
            }

//            for (Node nextNode : map[curNode.to]) {
//                if(!visited[nextNode.to]) {
//                    if(dp[curNode.to] + nextNode.weight < dp[nextNode.to]) {
//                        dp[nextNode.to] = dp[curNode.to] + nextNode.weight;
////                        q.offer(new Node(dp[nextNode.to], nextNode.to));
//                        q.offer(new Node(nextNode.to, dp[nextNode.to]));
//                    }
//
//                    visited[nextNode.to] = true;
////                    q.offer(new Node(dp[nextNode.to], nextNode.to));
//                }
//            }
        }
    }

    private static void input() 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()); //간선 수
//        map = new int[n+1][n+1]; //인덱스 0 버리기 (1부터 시작)
        map = new ArrayList[n+1];
        for (int i = 0; i < n+1; i++) {
            map[i] = new ArrayList<>(); //외우라고...
        }
        visited = new boolean[n+1];
        dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);

        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());

            map[a].add(new Node(b, c));
            map[b].add(new Node(a, c));
        }
    }
}
class Node implements Comparable<Node> { //컴퍼러블 상속 받아서 node 만들기 연습하기
    int to;
    int weight;

    public Node(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.weight, o.weight);
    }
}

 

 

연습할 것:

1. 다익스트라를 인접 리스트 + 우선순위 큐를 사용해 구현하기

1-1. 우선순위 큐를 만들기 위한 노드 클래스 만들기 연습(comparable 상속)

2. 초기화해야 할 게 정확히 뭔지 인지하기! (인접 행렬, 인접 리스트의 차이 때문에 생기는 문제)

2-1. 초기화 하지 말아야 할 것 -> 방문 배열, 두 번째 방문 값