[BOJ] 백준 1504 - 특정한 최단 경로 풀이

1. 문제

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

1504번: 특정한 최단 경로

2. 풀이

• 기본적인 다익스트라 알고리즘에 한 가지 아이디어를 추가하면 해결할 수 있는 문제이다.
• 이 문제의 핵심 포인트는 주어지는 입력의 마지막 줄인 반드시 거쳐야 하는 정점 v1, v2이다.
• 그렇다면 생각해볼 수 있는 것은 2가지가 있다.
  1. 1번 노드 -> v1 노드, v1 노드 -> v2 노드, v2 노드 -> N번 노드
  2. 1번 노드 -> v2 노드, v2 노드 -> v1 노드, v1 노드 -> N번 노드
• 다익스트라 함수를 구성하여 각각 비용의 최솟값을 구하고, 만약 결과 값이 두 경우 모두 처음에 설정한 최댓값이 나온 경우 경로가 없다는 이야기이므로 이럴 땐 "INF"를 출력한다.
• 주의할 점은 결과 값을 처음에 Integer의 MAX 값으로 할 경우 Overflow가 날 수 있기 때문에, 그보단 조금 작은 수로 설정하자.
  
  

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N; // 정점의 개수
    static int E; // 간선의 개수
    static int[] D; // 최솟값을 저장할 배열
    static boolean[] visited; // 방문 배열
    static class Node {
        int myV;        // 내 정점 번호
        int cost;

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

    static List<Node>[] nodeList; // 인접리스트

    static int result = Integer.MAX_VALUE / 4;
    static int resultFirst = 0;
    static int resultSecond = 0;

    static int first, second; // 꼭 방문해야 하는 정점들
    static BufferedReader br;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        // 인접 리스트 초기화
        nodeList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            nodeList[i] = new ArrayList<>();
        }

        // 인접리스트 연결
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            nodeList[from].add(new Node(to, cost));
            nodeList[to].add(new Node(from, cost));
        }

        // 꼭 방문해야 하는 정점
        st = new StringTokenizer(br.readLine());
        first = Integer.parseInt(st.nextToken());
        second = Integer.parseInt(st.nextToken());

        // 첫 번째 다익스트라
        sendDij(1, first, true);
        sendDij(first, second, true);
        sendDij(second, N, true);

        // 두 번째
        sendDij(1, second, false);
        sendDij(second, first, false);
        sendDij(first, N, false);

        //결과 출력
        if (resultFirst >= Integer.MAX_VALUE / 4 && resultSecond >= Integer.MAX_VALUE / 4) {
            bw.write("-1");
        } else {
            bw.write(Integer.toString(Math.min(resultFirst, resultSecond)));
        }
        bw.flush();
        bw.close();
        br.close();
    }

    // 다익스트라 전달 함수
    private static void sendDij(int start, int end, boolean flag) throws IOException {
        // D배열, 방문 배열 초기화
        D = new int[N + 1];
        visited = new boolean[N + 1];
        Arrays.fill(D, Integer.MAX_VALUE / 4);

        // start와 end가 같다면
        if (start == end) {
            return;
        } else {
            int t = minCostDij(start, end);

            if (flag) {
                resultFirst += t;
            } else {
                resultSecond += t;
            }
        }
    }

    // 다익스트라 함수
    private static int minCostDij(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost - o2.cost;
            }
        });

        // 시작 노드를 넣기
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if (!visited[node.myV]) {
                visited[node.myV] = true;
            }

            // 내 인접 노드를 확인
            for (int i = 0; i < nodeList[node.myV].size(); i++) {
                Node next = nodeList[node.myV].get(i);
                if (next != null) {
                    if (D[next.myV] > node.cost + next.cost) {
                        D[next.myV] = node.cost + next.cost;
                        pq.add(new Node(next.myV, D[next.myV]));
                    }
                }
            }
        }
        return D[end];
    }
}

4. 점수

90 / 100