백준 No.1504 특정한 최단 경로 - JAVA

 

 

문제

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

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

 

 

입력

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

 

주의사항

처음에 계속 주어진 입력을 넣었을 때 간단하게 답이 나왔는데 계속 틀려서 너무 화났는데 알고보니 문제에서 양방향이라는 말이 있는데 나는 코드에서 단방향을 만들어서 다시 돌아오지 못하는 경우였던 것이다.....

 

 

풀이

- 양방향으로 각 노드를 받는다

a ==> 시작
b ==> 끝
c ==> 가중치
graph.get(a).add(new Node(b,c)); //이거 하나만 하면 단방향
graph.get(b).add(new Node(a,c));

- 여기서 주어진 u,v를 거쳐서 가야한다. 거쳐서 간다는 것은 결국 해당 두 노드를 방문하는 최단 거리를 알아야한다.

근데 여기서는 주어진 값은 두 개이기에 u로 간 경우와 v로 간 경우 두가지 경로가 나오게 된다. 우리는 최단 경로를 구하는 것이기에 두가지 값 중에 작은 값을 선택하면 된다. (Math.min(u,v))

 

- 근데 주어진 문제는 주어진 노드를 거쳐서 가야하기 때문에 u를 거쳐서 N을 간 경우와 v를 거쳐서 N을 간 경우를 비교해야한다.

- 여기서 거쳐거쳐 가는 방법을 알아야 하는데 이 부분은 쪼개서 진행해야한다. sum 이라는 변수를 생성하고 해당 변수에 1(시작) u(도착) 까지의 최단거리를 다익스트라 알고리즘으로 구해서 sum에 더하고 u -> v 를 구해 더하고 v->N도 해당 알고리즘으로 구해서 더하면 된다. 이런 방식을 그대로 v로 갈때를 구해서 Math.min하면 된다.

- 문제에서 그러한 경로가 없을 때 -1을 출력하라 했다. dist 배열은 애초에 큰 값으로 모두 초기화하기 때문에 만약 sum이 비정상적으로 큰 값이 나온다면 최단경로를 구하지 못한 것이기에 -1 출력해버리면 된다.

 

 

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;

public class Main {
    static int N, E, u, v;
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int INF = 200000000;
    static boolean visited[];
    static int dijk[];

    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());    //간선의 개수
        dijk = new int[N + 1];
        visited = new boolean[N + 1];
        for (int i = 0; i <= N; i++) {
            graph.add(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.get(a).add(new Node(b, c));
            graph.get(b).add(new Node(a,c));
        }
        st = new StringTokenizer(br.readLine());
        u = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());   //두 정점 사이에 간선은 최대 1개가 존재한다.

        int sum1 = 0;
        sum1 += dijkstra(1,u);
        sum1 += dijkstra(u,v);
        sum1 += dijkstra(v,N);

        int sum2 = 0;
        sum2 += dijkstra(1,v);
        sum2 += dijkstra(v,u);
        sum2 += dijkstra(u,N);

        System.out.println((sum1 >= INF && sum2 >= INF) ? -1 : Math.min(sum1,sum2));
    }
    
    public static int dijkstra(int start,int end) {

        Arrays.fill(dijk, INF);
        Arrays.fill(visited, false);

        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        queue.add(new Node(start, 0));

        dijk[start] = 0;

        while (!queue.isEmpty()) {
            Node now = queue.poll();

            if (visited[now.v]) {
                continue;
            } else {
                visited[now.v] = true;
                for (Node next : graph.get(now.v)) {
                        if (!visited[next.v] && dijk[next.v] > dijk[now.v] + next.cost) {
                            dijk[next.v] = dijk[now.v] + next.cost;
                            queue.add(new Node(next.v, dijk[next.v]));
                        }
                    }
                }
        }
        return dijk[end];
    }

    static class Node {
        int v;
        int cost;

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