BOJ G4 1504 특정한 최단 경로 JAVA

1504번: 특정한 최단 경로

---

문제 읽기

방향성이 없는 그래프가 주어진다. 양방향이어도 다익스트라를 사용하는 데에는 전혀 문제가 없고, 단지 처음에 그래프를 인접 리스트로 입력 받을 때, 양 쪽에 다 넣어주면 된다.

 

일단 이 문제에서는 주어지는 두 노드를 반드시 방문하면서 1 → N까지의 최소 거리를 구해야 한다.

 

즉, 주어지는 두 노드를 mid1, mid2라고 한다면,

1 → mid1 → mid2 → N

또는

1 → mid2 → mid1 → N

 

이 두 경우만 고려하면 된다.

---

문제 풀기

두 경우에 따라 최종 결과를 구하는 식은 다음과 같다.

//1 -> mid1 -> mid2 -> N
ans1 = dist(1, mid1) + dist(mid1, mid2) + dist(mid2, N); 
//1 -> mid2 -> mid1 -> N
ans1 = dist(1, mid2) + dist(mid2, mid1) + dist(mid1, N); 

 

여기서

 

dist(1, mid1), dist(1, mid2)는 dijkstra(start=1)의 결과로 구할 수 있고,

dist(mid1, mid2) == dist(mid2, mi1)은 양방향 그래프이므로 값이 같기 때문에 dijkstra(start=mid1 or mid2)로 구할 수 있다.

마지막으로 dist(mid2, N) == dist(N, mid2), dist(mid1, N) == dist(N, mid1)이므로 dijkstra(start = N)으로 구할 수 있다.

 

그래서 나는 다익스트라를 3번만 사용했다.

1. 1을 출발점으로 다익스트라 1번,
2. mid1을 출발점으로 다익스트라 1번,
3. N을 출발점으로 다익스트라 1번

---

실수한 부분

INF 값의 설정

내가 푼 풀이 방식은 마지막에 dijkstra값을 세 번 더해줘야 한다. 따라서 dist의 초기 값인 INF가 너무 크면.. 오버플로우가 발생한다.

이것 때문에 8X퍼에서 계속 틀리다가 INF 값을 조정해주니까 통과됐다.

 

처음에는 INF를 Integer.MAX_VALUE - 1001로 했다가,

간선의 개수 E X 거리 c = 200,000 X 1,000 = 200000000로 했더니 통과되었다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G4_1504_특정한_최단경로 {
    static class Node{
        int no;
        int cost;
        public Node(int no, int cost){
            this.no = no;
            this.cost = cost;
        }
    }
    static int N, E;
    static ArrayList<Node>[] graph;
    static int mid1, mid2;
    static int[][] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N+1]; //1~N
        for (int i = 0; i < N+1; i++){
            graph[i] = new ArrayList<>();
        }
        while(E-- > 0){
            st = new StringTokenizer(in.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[start].add(new Node(end, cost));
            graph[end].add(new Node(start, cost)); //양방향
        }
        st = new StringTokenizer(in.readLine());
        mid1 = Integer.parseInt(st.nextToken());
        mid2 = Integer.parseInt(st.nextToken());

        //logic : dijkstra 3번
        dist = new int[3][N+1];
        dijkstra(1, 0);
        dijkstra(mid1, 1);
        dijkstra(N, 2);

        //print
        long ans1 = dist[0][mid1] + dist[1][mid2] + dist[2][mid2]; //1 -> mid1 -> mid2 -> N
        long ans2 = dist[0][mid2] + dist[1][mid2] + dist[2][mid1]; //1 -> mid2 -> mid1 -> N
        if (ans1 >= INF && ans2 >= INF) System.out.println("-1");
        else System.out.println((ans1 > ans2)? ans2 : ans1);
    }

    static int INF = 200000000; //2억
    private static void dijkstra(int start, int i) {
        //pq, visited
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost - o2.cost;
            }
        });
        boolean[] visited = new boolean[N+1];

        //init
        Arrays.fill(dist[i], INF);
        dist[i][start] = 0;
        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            if (visited[cur.no]) continue;
            visited[cur.no] = true;

            for (Node adj : graph[cur.no]){
                if (dist[i][adj.no] > dist[i][cur.no] + adj.cost){
                    dist[i][adj.no] = dist[i][cur.no] + adj.cost;
                    pq.offer(new Node(adj.no, dist[i][adj.no]));
                }
            }
        }
    }
}

---

의문점..

글 읽기 - 1504 특정한 최단경로 INF 값 정하기

위 글을 보고 INF 값을 800000으로 해서 제출했는데 60퍼에서 틀린다. 2억으로 하면 맞다. 왜지..???