[백준] 1504. 특정한 최단 경로

1. 문제

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

 

 

2. 풀이 과정

무방향 그래프가 주어질 때 시작점(1)에서 도착점(N)으로 가는 최단 경로를 구하는 문제이다. 여기까지는 일반적인 최단 경로를 구해서 문제를 해결 할 수 있다. 하지만 이 문제는 조건이 있다. 시작점에서 출발해 반드시 v1, v2 지점을 통과한 뒤 도착점까지의 최단 경로를 구해야 한다.

 

 문제 접근 방식

v1, v2 지점을 통과하는 최단 경로를 구하기 위해 두가지 케이스를 고려해야 한다.

• 1(시작점) -> v1 -> v2 -> N(도착점)
• 1(시작점) -> v2 -> v1 -> N(도착점) 

 

각각의 케이스에 따라 최단 경로를 구한 뒤, 둘 중에 더 작은 케이스의 결과를 출력해주면 된다.  

만약, 두 케이스 모두 INF 이상이라면 도달할 수 없기에 -1을 출력한다.

 

 

3. 코드

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static int E;

    static List<List<Point>> graph = new ArrayList<>();
    static int[] dist;
    static boolean[] visited;

    static final int INF = 200000 * 1000;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        visited = new boolean[N + 1];
        dist = new int[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 Point(b, c));
            graph.get(b).add(new Point(a, c));
        }

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

        int result1 = 0;
        result1 += dijkstra(1, v1);
        result1 += dijkstra(v1, v2);
        result1 += dijkstra(v2, N);

        int result2 = 0;
        result2 += dijkstra(1, v2);
        result2 += dijkstra(v2, v1);
        result2 += dijkstra(v1, N);

        if (result1 >= INF && result2 >= INF) {
            bw.write("-1\n");
        } else {
            bw.write(Math.min(result1, result2) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static int dijkstra(int start, int end) {
        Arrays.fill(dist, INF);
        Arrays.fill(visited, false);
        PriorityQueue<Point> pq = new PriorityQueue<>((o1, o2) -> o1.w - o2.w);

        pq.offer(new Point(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Point cur = pq.poll();
            if (visited[cur.end]) {
                continue;
            }
            visited[cur.end] = true;

            for (Point next : graph.get(cur.end)) {
                if (dist[next.end] > dist[cur.end] + next.w) {
                    dist[next.end] = dist[cur.end] + next.w;
                    pq.offer(new Point(next.end, dist[next.end]));
                }
            }
        }
        return dist[end];
    }

    static class Point {
        int end;
        int w;

        public Point(int end, int w) {
            this.end = end;
            this.w = w;
        }
    }
}