[BOJ/백준][JAVA] 5972 - 택배 배송

문제 풀기

5972번: 택배 배송

📒 문제

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

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

📒 해결방법

출발지와 도착지를 모두 알고 있는 그래프의 최단거리는 다익스트라로 해결해야 한다.
그래프의 최단거리 솔루션 알고리즘은 플로이드와샬이나 다익스트라가 있는데 출발지를 모를 때는 플로이드와샬로 모두 알고 있을 때는 다익스트라로 해결하는 것이 좋다고 한다. 
또한, 이 문제는 두 번이나 메모리 초과에 걸렸던 문제인데 이럴때는 배열보다는 ArrayList 가 좋고 INF설정을 50,000 * 1,000 + 1 즉, M의 최대* N의최대에 +1을 해주어 바로 해결하였다

📒 소스코드

package BOJ.Graph.dijkstra;

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

public class boj5972_택배배송 {
    static int N, M;
    static int[][] graph;
    static int INF = 50000001;
    static int[] dist;
    static ArrayList<Pair>[] list;

    static class Pair implements Comparable<Pair> {
        int to, weight;

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

        @Override
        public int compareTo(Pair o) {
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) throws Exception {
        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];
        list = new ArrayList[N + 1];

        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            list[v1].add(new Pair(v2, cost));
            list[v2].add(new Pair(v1, cost));
        }

        dijksta(1);

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

    static void dijksta(int start) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        boolean[] visit = new boolean[N + 1];
        Arrays.fill(dist, INF);

        dist[start] = 0;
        pq.offer(new Pair(start, 0));

        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            int dest = cur.to;

            if (visit[dest]) {
                continue;
            } else {
                visit[cur.to] = true;
            }

            for (Pair next : list[dest]) {
                if (dist[next.to] > dist[dest] + next.weight) {
                    dist[next.to] = dist[dest] + next.weight;
                    pq.offer(new Pair(next.to, dist[next.to]));
                }

            }
        }
    }
}

📒 리뷰

내 제출

 

---

메모리초과에 걸려서 조금 헤맸던 문제다.
INF를 줄 때 초반에 항상 Integer.MAX_VALUE로 주는 습관이 있었는데 앞으로는 최댓값을 확인해서 조절해서 줘야겠다!!

모두들 HAPPY NEW YEAR😘😘😘