[BOJ] 백준 1504번 : 특정한 최단 경로 (JAVA)

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

 

 

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

 

풀이

다익스트라 알고리즘을 약간 응용한 문제였습니다. 

 

다익스트라 알고리즘은 한 노드(start)에서 모든 노드 사이의 최단거리를 구할 수 있는 알고리즘입니다. 문제에서는 정점은 물론, 간선도 여러 번 이동할 수 있다고 합니다. 그리고 특정 노드 2개를 반드시 거쳐야한다고 명시되어있습니다.

 

언뜻 보면, 다익스트라 알고리즘을 어떻게 응용해야할 지 어려울 수 있으나 쉽게 생각하면 금방 해결됩니다.

바로 쪼개서 생각하는 것이죠.

 

원래 거쳐야하는 노드가 없다면, 1 -> N까지 다이렉트로 다익스트라 알고리즘을 1번만 실행하면 됩니다.

하지만, 거쳐야하는 노드가 있다면 아래와 같이 2가지 경우로 나누어서 생각해야 합니다.

(이 때, 거쳐야하는 노드를 v1과 v2로 표현하겠습니다.)

 

(1) 1 -> v1 -> v2 -> N

(2) 1 -> v2 -> v1 -> N

 

1번 케이스의 경우, 1에서 v1까지 다익스트라 알고리즘을 수행, v1에서 v2까지 다익스트라 알고리즘을 수행, N까지 다익스트라 알고리즘을 수행하면 됩니다. 그리고 각각의 최단 거리에 대해서 모두 더합니다.

 

2번 케이스도 마찬가지로 최단 거리를 더하고, 1번 케이스에서 구한 결과값과 비교해서 더 작은 값을 정답으로 출력하면 됩니다.

 

다만, 1번과 2번 케이스에서 얻어낸 값이 INF보다 크거나 같다면 v1과 v2를 거쳐서 N에 도달할 수 없다는 의미이므로 -1을 출력하면 됩니다.

 

여기서, INF를 설정하는 데 있어서 주의를 해야 합니다. 저는 처음에 아무 생각 없이 Integer.MAX.VALUE로 int의 최댓값을 설정했는데, 오버플로우가 발생해서 틀렸습니다.

 

그렇다면, INF는 몇으로 설정해야할까요? 바로, 200,000,000입니다. 이유는 단순합니다. 간선의 최대 개수는 200,000이고, 가중치의 최댓값은 1,000이기 때문이죠.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Node implements Comparable<Node> {
    int end;
    int weight;
 
    Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
 
}
 
public class Main {
    static int N, E;
    static ArrayList<ArrayList<Node>> a; // 인접리스트.
    static int[] dist; // 시작점에서 각 정점으로 가는 최단거리.
    static boolean[] check; // 방문 확인.
    static final int INF = 200000000;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
 
        a = new ArrayList<>();
        dist = new int[N + 1];
        check = new boolean[N + 1];
 
        Arrays.fill(dist, INF);
 
        for (int i = 0; i <= N; i++) {
            a.add(new ArrayList<>());
        }
 
        // 양방향 인접 리스트 구현.
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            // start에서 end로 가는 weight (가중치)
            a.get(start).add(new Node(end, weight));
 
            // end에서 start로 가는 weight (가중치)
            a.get(end).add(new Node(start, weight));
        }
 
        // 반드시 거쳐야 하는 정점.
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int 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);
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 다익스트라 알고리즘
    public static int dijkstra(int start, int end) {
        Arrays.fill(dist, INF);
        Arrays.fill(check, false);
 
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] check = new boolean[N + 1];
        pq.offer(new Node(start, 0));
        dist[start] = 0;
 
        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            int cur = curNode.end;
 
            if (!check[cur]) {
                check[cur] = true;
 
                for (Node node : a.get(cur)) {
                    if (!check[node.end] && dist[node.end] > dist[cur] + node.weight) {
                        dist[node.end] = dist[cur] + node.weight;
                        pq.add(new Node(node.end, dist[node.end]));
                    }
                }
            }
        }
 
        return dist[end];
    }
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.