BOJ_1504 : 특정한 최단 경로

👉 문제링크

1504번: 특정한 최단 경로

---

---

🔸 문제 분석 🔸

• N개의 노드와 E개의 간선이 있다.
  • 1번 노드부터 N번 노드까지의 최단거리를 구하는데 v1과 v2 노드를 경유해야 한다.
• 다익스트라 알고리즘의 활용으로 풀이 가능하다. (난 프림 알고리즘으로 생각했다)
  • 경로는 2가지 종류가 있다. (1 > A > B > N , 1 > B > A > N)
    • 첫 번째 경우는 1 > A, A > B, B > N 의 최단거리를 각각 구해야 한다.
    • 두 번째 경우는 1 > B, B > A, A > N 의 최단 거리를 각각 구해야 한다.
    • 무방향 간선이므로 A > B와 B > A는 같다.
  • 총 3번의 다익스트라로 값을 구할 수 있다.
    1. 1부터 A와 1부터 B
    2. A부터 B, A부터 N
    3. B부터 N
  • 두 경우에서 더 짧은 경우를 골라 출력한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static class Edge implements Comparable<Edge> {
        int node, weight;

        public Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

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

    private static ArrayList<Edge>[] adjList;
    private static int[] dist;
    private static final int INF = 200_000_000;

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

        int N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        adjList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adjList[a].add(new Edge(b, c));
            adjList[b].add(new Edge(a, c));
        }

        st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        // prim
        dist_init(N + 1);
        prim(1);
        int StoA = dist[A];
        int StoB = dist[B];
//        System.out.println(Arrays.toString(dist));

        dist_init(N + 1);
        prim(A);
        int AtoB = dist[B];
        int AtoN = dist[N];
//        System.out.println(Arrays.toString(dist));

        dist_init(N + 1);
        prim(B);
        int BtoN = dist[N];
//        System.out.println(Arrays.toString(dist));

        // Output
        int res = INF;
        int SABN = StoA + AtoB + BtoN;
        int SBAN = StoB + AtoB + AtoN;

        res = Math.min(res, SABN);
        res = Math.min(res, SBAN);

        if (AtoB == INF || res == INF)
            bw.write("-1");
        else {
            bw.write(Integer.toString(res));
        }
        bw.flush();
    }

    private static void prim(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();

            if (dist[edge.node] < INF) continue;
            dist[edge.node] = edge.weight;

            for (Edge e : adjList[edge.node]) {
                if (dist[e.node] > edge.weight + e.weight)
                    pq.add(new Edge(e.node, edge.weight + e.weight));
            }
        }
    }

    private static void dist_init(int N) {
        dist = new int[N];
        Arrays.fill(dist, INF);
    }
}

🔸 코드 해석 🔸

• 다익스트라 알고리즘에서 우선순위 큐에 사용 할 간선 클래스 Edge를 선언했다.
• 노드의 간선 정보를 저장할 인접 리스트 배열 adjList를 선언했다.
• 최단 거리 정보를 저장할 배열 dist를 선언했다.
• 문제에서 간선의 최대 수는 20만개이고, 가중치는 1,000까지 이므로 무한대 값은 2억으로 두고 INF에 저장해서 사용했다.
• 3번의 다익스트라 알고리즘을 돌리고 결과를 비교해 최소값을 출력했다.
• 결과가 무한대가 나오면 -1을 출력한다.

---

🔸 end 🔸

• 다익스트라 활용 문제로 간단한 것 같은데, 풀때는 아주 고생을 많이 한 문제이다.
  • 처음엔 BFS로 접근해서 v1, v2 노드 방문 여부를 큐에서 들고다녔더니 메모리 초과가 났다.
  • 두 번째로 다익스트라 + 방문 여부를 들고 다니기였는데 또 메모리 초과가 났다.
  • 결국 풀이 포스팅을 참고했다. (풀이 포스팅)
• 75%에서 2번 틀렸는데, 출력 결과가 -1이 잘 찍히지 않아서 그랬다.
  • 최종 결과가 -1이 잘 나와야하는데, INF 값을 Integer.MAX_VALUE로 두면 overflow가 나서 제대로 계산되지 않았다.
  • INF를 따로 2억으로 선언하는 방법으로 해결했다.
• 다익스트라라곤 하지만 풀이를 보니 프림에 가깝다고 생각해서 메서드 명은 prim으로 풀이했다.
• 생각보다 너무 고생해서 다익스트라 연습이 더 필요하다고 절실히 느꼈다.