[BaekJoon] 1504번 특정한 최단 경로 (Java) 문제 풀이 [Gold 4]

문제

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

어떻게 풀 것인가?

최단경로 다익스트라 알고리즘을 사용하여 풀어야하는 문제이다.

하지만 무조건 V1와 V2를 지나야 한다.

 

해결법은 간단하다. 

 

시작점 -> V1 까지 가는 최단경로 비용

V1 -> V2 까지 가는 최단경로 비용

V2 -> 목적지 까지 가는 최단경로 비용 

 

즉, 최단경로를 3번 사용하여 

위3개의 최단경로 비용의 합을 구하면 된다.

 

단 위와 같이만 하면 문제는 틀리다고 뜰 것이다.

왜냐하면 시작점 -> V1까지 가는 최단경로의 비용이 시작점 -> V2 가는 최단경로의 비용보다 더 클 수도 있기 때문이다.

 

그렇기때문에

시작점 -> V2 까지 가는 최단경로 비용

V2 -> V1 까지 가는 최단경로 비용

V1 -> 목적지 까지 가는 최단경로 비용 

 

와 같은 로직을 또 사용하여, 

 

전자와 후자를 비교하여 더 적게 나온 최단경로 비용을 도출하면 정답이 된다.

 

풀면서 놓쳤던점

X

 

이 문제를 통해 얻어갈 것

다익스트라 알고리즘의 응용.

 

내 코드 

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;

// 백준알고리즘 1504번 특정한 최단 경로
public class Main {
    static int N, E;

    static int v1, v2;
    static ArrayList<Node>[] graph;
    static final int INF = 200000000;

    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());
        E = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) graph[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());
            graph[a].add(new Node(b, c));
            graph[b].add(new Node(a, c));

        }
        st = new StringTokenizer(br.readLine());
        v1 = Integer.parseInt(st.nextToken());
        v2 = Integer.parseInt(st.nextToken());

        // 1 -> v1 -> v2 -> N으로 가는 경우
        int res1 = 0;
        res1 += Dijkstra(1, v1);
        res1 += Dijkstra(v1, v2);
        res1 += Dijkstra(v2, N);

        // 1 -> v2 -> v1 -> N으로 가는 경우
        int res2 = 0;
        res2 += Dijkstra(1, v2);
        res2 += Dijkstra(v2, v1);
        res2 += Dijkstra(v1, N);

        int ans = (res1 >= INF && res2 >= INF) ? -1 : Math.min(res1, res2);

        System.out.println(ans);
    }

    public static int Dijkstra(int start, int end) {
        // 출발지 -> v1
        boolean[] check = new boolean[N + 1];
        int[] dist = new int[N + 1];

        Arrays.fill(dist, INF);
        Arrays.fill(check, false);

        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            int nowVertex = pq.poll().index;

            if (check[nowVertex]) continue;
            check[nowVertex] = true;

            //index의 연결된 정점 비교
            for (Node next : graph[nowVertex]) {
                if (!check[next.index] && dist[next.index] > dist[nowVertex] + next.cost) {
                    dist[next.index] = dist[nowVertex] + next.cost;

                    pq.offer(new Node(next.index, dist[next.index]));
                }
            }
        }

        return dist[end];
    }
}

class Node implements Comparable<Node> {
    int index;
    int cost;

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

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

 

참고

X