[백준 1504 : JAVA] 특정한 최단 경로 / 다익스트라

개요

 

다익스트라 알고리즘을 이용하여 약간의 응용(?)을 하면 풀이가 가능하다.

다익스트라가 처음이라면 아래의 문제를 먼저 풀고 오는 것을 추천한다.

 

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

1753번: 최단경로

위 문제의 풀이는 아래 링크를 참조할 수 있다.

2020/02/09 - [알고리즘/백준] - [백준 1753 : JAVA] 최단경로 / 다익스트라

[백준 1753 : JAVA] 최단경로 / 다익스트라

문제

 

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

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

 

입력

 

풀이

 

이 문제는 1 -> N 까지 두 개의 주어진 정점을 지나면서 가는 최단거리를 구하는 문제이다.

그리고 최단경로를 위해서는 한 정점을 중복하여 지날 수 있고 간선 또한 마찬가지이다.

필수 정점은 M1, M2로 표현하겠다.

 

두 가지 경우를 계산하여 둘 중에 최솟값을 출력하면 된다.

이때 두 가지 경우 모드 INF보다 크거나 같다면 경로가 없는 것이므로 -1을 출력한다.

 

1. 1 -> M1 -> M2 -> N으로 가는 최단거리

2. 1 -> M2 -> M1 -> N으로 가는 최단거리

 

1 경우는  1 -> M1 최단거리, M1 -> M2 최단거리, M2 -> N의 최단거리를 각각 다익스트라를 통해 구한 뒤 더해준다.

2 경우는  1 -> M2 최단거리, M2 -> M1 최단거리, M1 -> N의 최단거리를 각각 다익스트라를 통해 구한 뒤 더해준다.

 

 

코드

import java.io.*;
import java.util.*;

class Point implements Comparable<Point>{
    int end;
    int weight;

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

    @Override
    public int compareTo(Point o) {
        return weight - o.weight;
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 200_000_000;
    static List<Point> list[];
    static int dist[];
    static boolean check[];
    static int n, v;


    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        // 그래프 정보 저장할 list를 초기화한다.
        list = new ArrayList[n + 1];
        for(int i = 0; i <= n; i++)
            list[i] = new ArrayList<>();

        dist = new int[n + 1];
        check = new boolean[n + 1];

        // 간선 정보 초기화
        for(int i = 0 ; i < v; i++){
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            // list에 graph정보 저장 list의 index는 출발노드
            // element는 도착노드와 가중치를 저장한다.
            list[start].add(new Point(end, weight));
            // 무방향 그래프이므로 반대도 추가해준다.
            list[end].add(new Point(start, weight));
        }

        // 필수 노드 초기화
        st = new StringTokenizer(br.readLine());
        int require1 = Integer.parseInt(st.nextToken());
        int require2 = Integer.parseInt(st.nextToken());

        // 풀이 메소드 호출
        int answer = solve(require1, require2);
        bw.write(answer+ "\n");

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

    private static int solve(int required1, int required2){
        int result1 = 0;
        int result2 = 0;

        // 경로1
        // 1 -> 필수1 최단거리
        result1 += dijkstra(1, required1);
        // 필수1 -> 필수2 최단거리
        result1 += dijkstra(required1, required2);
        // 필수2 -> n 최단거리
        result1 += dijkstra(required2, n);

        //경로2
        // 1 -> 필수2 최단거리
        result2 += dijkstra(1, required2);
        // 필수2 -> 필수1 최단거리
        result2 += dijkstra(required2, required1);
        // 필수1 -> n 최단거리
        result2 += dijkstra(required1, n);

        // 경로1 && 경로2 -> 가는길이 없는 경우
        if(result1 >= INF && result2 >= INF) return -1;
        else return Math.min(result1, result2);
    }

    private static int dijkstra(int start, int end){
        Arrays.fill(dist, INF);
        Arrays.fill(check, false);

        PriorityQueue<Point> queue = new PriorityQueue<>();
        queue.add(new Point(start, 0));
        dist[start] = 0;

        while (!queue.isEmpty()){
            Point curPoint = queue.poll();
            int curNode = curPoint.end;
            int curWeight = curPoint.weight;

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

            for(int i = 0; i < list[curNode].size(); i++){
                int nextNode = list[curNode].get(i).end;
                int nextWeight = list[curNode].get(i).weight;
                // 미방문 && 기존의 계산된 거리보다 새로운 거리가 작을 경우
                if(check[nextNode] == false && dist[nextNode] > curWeight + nextWeight){
                    dist[nextNode] = curWeight + nextWeight;
                    queue.add(new Point(nextNode, dist[nextNode]));
                }
            }
        }
        return dist[end];
    }
}