📖 [백준알고리즘 풀이] Q.1504 특정한 최단 경로

📖 문제

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

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다.

또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데,

그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다.

하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때,

주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

🔍 접근법

BOJ Q.1504 특정한 최단 경로 문제입니다.

기본 바탕은 다익스트라 알고리즘으로 풀이가 가능합니다.

여기서 다소 다른 것은 임의로 주어진 두 정점을 반드시 통과해야 한다는 것 입니다.

도착지까지 정점 1 , 정점 2 를 반드시 통과하는 경우는 다음과 같습니다.

시작 -> 정점1 -> 정점2 -> 끝 시작 -> 정점2 -> 정점1 -> 끝

이렇게 두가지 경우중에 더 최단 경로를 찾으면 풀이가 가능합니다.

solve 함수 => 다익스트라 알고리즘을 이용해 주어진 시작점부터 끝까지의 최단경로를 구하는 함수 solve 함수를 이용해 아래와 같이 시작 -> 정점1 -> 정점2 -> 끝 시작 -> 정점2 -> 정점1 -> 끝

두가지 중 더 짧은 경로가 특정한 최단 경로입니다.

             answer[0] += solve(1,first)+solve(first,second)+solve(second,N);
             answer[1] += solve(1,second)+solve(second,first)+solve(first,N);

💻 코드

package problem.shortest.Q1504;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main_1504 {

    static class Node implements Comparable<Node>{
        int index;
        int distance;

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

        @Override
        public int compareTo(Node target) {
            // 작은 거리 비용이 먼저 오도록
            return this.distance - target.distance;
        }
    }

    static final int INF = 100000000;
    static int N, M, start,end;
    static List<List<Node>> adList;
    static int[] distance;
    static boolean[] visited;
    static PriorityQueue<Node> priorityQueue;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer[] = {0,0};

        String input[] = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        adList = new ArrayList<>();
        // 인덱스를 1부터 하기 위해서 한 개를 넣어둠
        adList.add(new <Node>ArrayList());
        for (int i = 1; i <= N; i++) {
            adList.add(new <Node>ArrayList());
        }

        for (int i = 0; i < M; i++) {
            String[] temp = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);
            int cost = Integer.parseInt(temp[2]);
            adList.get(u).add(new Node(v, cost));
            adList.get(v).add(new Node(u, cost));
        }

        input = br.readLine().split(" ");
        int first = Integer.parseInt(input[0]);
        int second = Integer.parseInt(input[1]);

        answer[0] += solve(1,first)+solve(first,second)+solve(second,N);
        answer[1] += solve(1,second)+solve(second,first)+solve(first,N);

        int shortestPathCost = Integer.min(answer[0],answer[1]);
        if(shortestPathCost>=INF)
            System.out.println(-1);
        else
            System.out.println(shortestPathCost);
    }

    private static int solve(int start , int end) {
        priorityQueue = new PriorityQueue<>();
        visited = new boolean[N +1];
        distance = new int[N + 1];
        Arrays.fill(distance, INF);

        distance[start] = 0;
        priorityQueue.add(new Node(start, 0));

        while(!priorityQueue.isEmpty()) {
            Node current =  priorityQueue.poll();

            if(visited[current.index]){
                continue;
            }
            visited[current.index] = true;
            // 연결된 정점들을 확인
            for(Node destination : adList.get(current.index)) {
                //목적지 직행 , 현재까지 거리 + 현재에서 목적지 거리
                if(distance[destination.index] > distance[current.index] + destination.distance) {
                    // 최소 거리 비용 갱신
                    distance[destination.index] = distance[current.index] + destination.distance;
                    priorityQueue.add(new Node(destination.index, distance[destination.index]));
                }
            }
        }
        return distance[end];
    }
}
}

Written on October 24, 2020