99클럽 코테 스터디2 - 5일차(다익스트라)

문제 : https://www.acmicpc.net/problem/17270

🚨 오늘의 학습

⭐️ 플로이드 워셜

각 노드를 거쳐가는 모든 경로의 최단거리 구하는 알고리즘
최단거리 배열은 2차원 배열 = dist[][]

🔅플로이드 워셜 조건

• 음의 사이클 존재 X
• 음의 가중치 가능
• 노드가 100개 이하(메모리 고려)

🗝️ 지헌과 성하가 최단거리의 만나는 지점 구하기

1. 각 출발 지점에서 만날 수 없다
2. 최단거리 지점에서 만난다
3. 지헌이 먼저 도착하거나 지헌과 성하가 동시에 도착 할 수 있는 지점
   (※ 지헌이 성하보다 늦는 경우 제외)
4. 만약 여러 지점이 있다면 지헌이에게 더 가까운 지점에서 만난다
5. 4번 경우의 노드가 여러개라면 번호가 제일 적은 노드번호를 출력한다

🗝️ 플로이드 워셜 vs 다익스트라

• 최단거리 알고리즘에 가장 효율적

방법 1 (다익스트라)

✅ 지헌의 출발점이 하나로 고정, 성하의 출발점이 하나로 고정
✅ 지헌▶️성하, 지헌◀️성하 각 최단경로 중 조건에 만족하는 지점 구하기

import java.util.*;

public class Main {

    static final int INF = Integer.MAX_VALUE;
    static int N, M;
    static int J, S;
    static ArrayList<Pair>[] connect;
    static int[] J_Distance = new int[101]; // J -> X를 저장
    static int[] S_Distance = new int[101]; // S -> X를 저장

    static class Pair {
        int first, second;
        
        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    // 거리 배열을 초기화
    public static void resetDistance(int[] dist) {
        Arrays.fill(dist, INF);
    }

    // 다익스트라 알고리즘
    public static void dijkstra(int start, int[] dist) {
        resetDistance(dist);
        dist[start] = 0;
        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.second));
        pq.offer(new Pair(start, 0));

        while (!pq.isEmpty()) {
            Pair current = pq.poll();
            int x = current.first;
            int cost = current.second;

            if (dist[x] < cost) continue;

            for (Pair neighbor : connect[x]) {
                int xx = neighbor.first;
                int nCost = cost + neighbor.second;
                if (dist[xx] > nCost) {
                    dist[xx] = nCost;
                    pq.offer(new Pair(xx, dist[xx]));
                }
            }
        }
    }

    public static void solve() {
        int JS_distance = INF;
        int point = -1, J_dis = INF;

        // 지헌이부터 출발해 다른 지점까지 걸리는 비용
        dijkstra(J, J_Distance);
        // 성하부터 출발해 다른 지점까지 걸리는 비용
        dijkstra(S, S_Distance);

        // 최소 거리를 구함
        for (int i = 1; i <= N; i++) {
            if (i == J || i == S) continue;
            JS_distance = Math.min(JS_distance, J_Distance[i] + S_Distance[i]);
        }

        // 조건에 맞는 최적의 점을 찾음
        for (int i = N; i >= 1; i--) {
            if (i == J || i == S) continue;
            if (JS_distance != J_Distance[i] + S_Distance[i]) continue;
            
            // J와 S가 동시에 도달하는 지점도 허용
            if (J_Distance[i] > S_Distance[i] && J_Distance[i] != S_Distance[i]) continue;

            if (J_dis >= J_Distance[i]) {
                J_dis = J_Distance[i];
                point = i;
            }
        }

        System.out.println(point);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        connect = new ArrayList[N + 1];
        
        for (int i = 1; i <= N; i++) {
            connect[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int cost = sc.nextInt();
            connect[x].add(new Pair(y, cost));
            connect[y].add(new Pair(x, cost));
        }

        J = sc.nextInt();
        S = sc.nextInt();

        solve();
    }
}

방법 2(플로이드-워셜)

https://www.acmicpc.net/problem/11404
https://www.acmicpc.net/problem/1507
https://www.acmicpc.net/problem/2458