1. 문제 설명 📌

지헌과 성하의 새로운 약속 장소를 찾아주는 문제로서, 다익스트라를 통해 각자의 출발점에서 모든 정점까지의 최소 도달 비용을 구하고, 이를 통해 4가지 조건을 만족하는 약속 장소를 찾으면 된다.

하지만, 출제자가 지문을 되게 모호하게 적어서, 조건의 진의가 헷갈린다.

약속 장소의 조건은 다음과 같다.

1️⃣ 각자의 출발점은 약속 장소가 될 수 없다.
2️⃣ 둘 다 최소 비용으로 닿을 수 있는 장소여야 한다.
3️⃣ 지헌이가 성하보다 먼저 도착하는 장소여야 한다.
4️⃣ 위의 조건을 모두 만족하는 장소가 복수라면, 그 중 지헌이가 빨리 도착하는 장소를 고른다. (이 마저도 복수이면, 정점 번호가 빠른 것을 고른다.)

이 조건을 보면,
각자의 출발점이 아니면서, 지헌이가 성하보다 먼저 도착하면서, 지헌이가 가능한 빠르게 도착하는 장소 라는 의미로 받아들일 수 있다. (즉, 모두가 AND로 역여있다고 생각해서, 조건의 순서를 무시해도 된다고 생각한다는 것이다.)

다른 문제였다면, 이러한 발상은 맞으나, 이 문제는 그렇게 조건의 순서를 무시하면 틀린다. 근데 이는, 풀이자의 해석 착오가 아니라, 출제자가 문제를 모호하게 기술한 탓이라 생각한다. 여튼 문제를 풀려면, 조건을 순서대로 만족시키는 정점을 찾아야 한다. 즉

1️⃣ 시작 정점, 도착 정점 제외
2️⃣ 모든 정점 중 둘의 이동 비용을 합쳤을 때, 최소 비용이 드는 정점말고 모두 제외
3️⃣ 그 중 지헌이가 성하보다 늦게 도착하는 정점 제외
4️⃣ 그 중 지헌이가 제일 빨리 도착하는 정점 고르기 (없으면 정점 번호 빠른 순)

2. 구현 방법 🗃️

KEY WORD: DIJKSTRA

1️⃣ 인접리스트로 그래프 구현 및, 각자의 거리배열 생성
2️⃣ 각자의 출발점에서 다익스트라 돌려서 거리 배열 완성
3️⃣ 4가지 조건을 차례대로 확인하며, 조건에 부합하지 않는 정점 제거해나가기
4️⃣ 4번조건까지 하고 남은 것들 중 지헌이가 가장 빨리 도착하는 것, 그 중에서도 정점 번호가 빠른 것을 출력

(1) 시간복잡도 분석 🕓

다익스트라를 우선순위 큐로 구현했기 때문에, 정점의 수를 V, 간선의 수를 M이라고 할 때,

$O(V \log M)$

3. 코드 소개 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int V, M, J, S;
    static long min_dist, J_smallest_dis, ans;
    static long [] distJ, distS;                 // 지헌이 최단거리, 성하 최단거리
    static ArrayList<Node>[] lists;
    static ArrayDeque<Node> land_of_promise = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        lists = new ArrayList[V + 1];
        distJ = new long [V + 1];
        distS = new long [V + 1];
        Arrays.fill(distJ, Integer.MAX_VALUE);
        Arrays.fill(distS, Integer.MAX_VALUE);
        for (int i = 1; i < V + 1; i++) {
            lists[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start   = Integer.parseInt(st.nextToken());
            int end     = Integer.parseInt(st.nextToken());
            int weight  = Integer.parseInt(st.nextToken());
            lists[start].add(new Node(end, weight));
            lists[end].add(new Node(start, weight));
        }
        st = new StringTokenizer(br.readLine());
        J = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        dijkstar(true);
        dijkstar(false);

//        System.out.println("지현: " + Arrays.toString(distJ));
//        System.out.println("성하: " + Arrays.toString(distS));

        min_dist = Integer.MAX_VALUE;
        for (int i = 0; i < V + 1; i++) {
            if( i == J || i == S) continue;
            min_dist = (int)Math.min(min_dist, distJ[i] + distS[i]);
        }

        ans = -1;
        J_smallest_dis = Integer.MAX_VALUE;
        for (int i = V ; i >= 1; i --) {
            if( i == J || i == S) continue;
            if(min_dist != distJ[i] + distS[i]) continue;
            if(distJ[i] > distS[i]) continue;
            if(J_smallest_dis >= distJ[i]) {
                J_smallest_dis = distJ[i];
                ans = i;
            }
        }
        System.out.println(ans);
    }

    public static void dijkstar (boolean isJ) {
        int START = isJ? J : S;
        long [] dist = isJ? distJ : distS;
        PriorityQueue<Dist> pq = new PriorityQueue<>(Comparator.comparingLong(o -> o.dist));
        dist[START] = 0;
        pq.add(new Dist(START, 0));

        while(!pq.isEmpty()) {
            Dist now = pq.poll();

            if(now.dist != dist[now.idx]) continue;

            for (int i = 0; i < lists[now.idx].size(); i++) {
                Node next = lists[now.idx].get(i);
                if(dist[next.idx] > dist[now.idx] + next.w){
                    dist[next.idx] = dist[now.idx] + next.w;
                    pq.add(new Dist(next.idx, dist[next.idx]));
                }
            }
        }
    }
}

class Node {
    int idx;
    int w;

    public Node (int idx, int w){
        this.idx = idx;
        this.w = w;
    }
}

class Dist {
    int idx;
    long dist;

    public Dist(int idx, long dist){
        this.idx= idx;
        this.dist = dist;
    }
}

(1) 정점 나타내는 클래스 2개 씀

Dist 클래스는 다익스트라에서 <도착정점, 시작점에서 도착 정점까지 최소 비용> 을 나타내기 위해 사용했고, Node는 인접 리스트에서 <도착 정점, 가중치>를 나타내기 위해 사용했다. 둘을 겹쳐 써도 되나, 코드 작성 중 헷갈릴 듯 싶어 나누었다.

(2) 마지막에 거리 배열을 뒤에서부터 계산

        for (int i = V ; i >= 1; i --) {
            if( i == J || i == S) continue;
            if(min_dist != distJ[i] + distS[i]) continue;
            if(distJ[i] > distS[i]) continue;
            if(J_smallest_dis >= distJ[i]) {
                J_smallest_dis = distJ[i];
                ans = i;
            }
        }

J_smallest_dis는 지헌이가 가장 빨리 도착하는 정점까지의 비용을 나타낸다. 위 비교를 보면, 현재 보고있는 정점까지 지헌이가 가는 비용과 J_smallest_dis가 같아도 갱신한다. 이는 조회를 역순으로 하기 때문에 자연스럽게, 비용이 같다면 더 작은 idx가 답이 되도록 만든 것이다.