(백준) 가운데서 만나기 - 21940

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

21940번: 가운데에서 만나기

 

🐢문제

친구들과 만나기 위한 중간 지점을 구해야하는 문제이다. 양방향 그래프가 아닌 단방향 그래프이고, 주어진 친구 위치에서 다른 모든 정점으로 도로가 있는 것이 아니므로 주의해야한다.

각 친구 위치에서 모든 정점을 중간위치 x로 놓고 비교해서 특정 x일 때 왕복거리가 가장 높은 값이 가장 낮도록 하는 x를 구하면 된다.

 

🐢해설

x를 구하기 위해서 다익스트라 방법과 플로이드와샬 방법을 사용할 수 있는데, 단방향이므로 친구들의 위치에서만 다익스트라를 구하면 되돌아 오는 최적의 거리를 알 수 없다. 그러면 결국 모든 정점에 대해서 다익스트라를 구해야 하므로 플로이드 와샬 방법을 사용하는 것이 더 적합하다.

 

먼저 모든 정점을 INF로 초기화 하고, 주어진 거리와 자기 자신에 대한 거리를 넣어준다. 이 후 모든 정점을 중간 위치로 놓고 해당 중간 위치x에 대해서 친구1 -> x, x -> 친구1 / 친구 2 -> x, x -> 친구 2 .. 식으로 모든 왕복 거리를 구해서 최대값을 갱신하고, 해당 최대값들 중 최소값을 구하면된다. 이때 왕복최대값이 최소값과 동일하다면 후보군에 들 수 있으므로 추가해고 그렇지 않다면 리스트를 초기화해서 다시 넣어주면 된다. 

 

🐢코드

//package Gold이상문제_정리;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K, S, INF = 1000000;
    static int[][] cost;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        cost = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            Arrays.fill(cost[i], INF);
            cost[i][i] = 0;
        }
 
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()) - 1;
            int e = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken());
            cost[s][e] = c;
        }
 
        S = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] friends = new int[S];
        for (int i = 0; i < S; i++)
            friends[i] = Integer.parseInt(st.nextToken()) - 1;
 
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (cost[i][k] == INF || cost[k][j] == INF) continue;
                    if (cost[i][j] > cost[i][k] + cost[k][j]) {
                        cost[i][j] = cost[i][k] + cost[k][j];
                    }
                }
            }
        }
 
        ArrayList<Integer> candidate = new ArrayList<>();
        int minTotal = INF;
        int maxGoBack;
        for (int x = 0; x < N; x++) {
            maxGoBack = 0;
            for (int friend : friends) {
                int go = cost[friend][x];
                int back = cost[x][friend];
 
                if (go == INF || back == INF) {
                    maxGoBack = INF;
                    break;
                }
 
                if (maxGoBack < go + back)
                    maxGoBack = go + back;
            }
            if (minTotal > maxGoBack) {
                minTotal = maxGoBack;
                candidate.clear();
                candidate.add(x + 1);
            } else if (minTotal == maxGoBack)
                candidate.add(x + 1);
        }
 
        StringBuilder ans = new StringBuilder();
        for (int x : candidate)
            ans.append(x).append(" ");
        System.out.println(ans);
    }
}