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

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

 

문제

준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다.

도시를 연결하는 도로는 일방 통행만 있어서 도시 𝐴에서 도시 𝐵로 가는 시간과 도시 𝐵에서 도시 𝐴로 가는 시간이 다를 수 있다.

준형이와 친구들은 아래 조건을 만족하는 도시 𝑋를 선택하여 거기서 만나려고 한다.

• 왕복시간은 자신이 살고 있는 도시에서 도시 𝑋로 이동하는 시간과 도시 𝑋에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다.
• 준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다.
• 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 𝑋를 선택한다.
• 준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다.

도시가 많다보니 계산하기 힘들다. 준형이와 친구들을 대신하여 도시 𝑋를 알려주자.

 

유형 : 플로이드 - 워셜

 

접근 방식

• 단방향 간선이다. N의 크기가 200이기 때문에 플로이드 - 워셜 알고리즘을 통해 각 정점 간의 거리를 구한다.
• 하나의 출발점을 기준으로 준형이와 친구들의 거리의 최댓값을 구한다. 거리 값은 dis[start][i] + dis[i][start] 이다.

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int n,m,k;
    static int[][] board;

    static int[] input;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][n+1];

        for(int i = 1 ; i <= m ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            int num = board[v1][v2] == 0 ? c : Math.min(board[v1][v2],c);

            board[v1][v2] = num;
        }

        st = new StringTokenizer(br.readLine()," ");
        k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()," ");
        input = new int[k+1];

        for(int i = 1 ; i <= k ; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        for(int k = 1 ; k <= n ; k++) {
            for(int i = 1 ; i <= n ; i++) {
                for(int j = 1 ; j <= n ; j++) {
                    if(i == j)
                        continue;

                    if(board[i][k] == 0 || board[k][j] == 0)
                        continue;

                    int num = board[i][j] == 0 ? board[i][k] + board[k][j] : Math.min(board[i][j], board[i][k] + board[k][j]);

                    board[i][j] = num;
                }
            }
        }

        int[] result = new int[n+1];

        int min = Integer.MAX_VALUE;

        for(int i = 1 ; i <= n ; i++) {
            int nextNum = cal(i);

            result[i] = nextNum;

            if(result[i] == -1)
                continue;

            min = Math.min(min,result[i]);
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 1 ; i <= n ; i++) {
            if(min == result[i])
                sb.append(i+" ");
        }sb.append("\n");

        System.out.print(sb.toString());

        br.close();
    }

    static int cal(int start) {

        int result = 0;

        for(int i = 1 ; i <= k ; i++) {

            int nextPoint = input[i];

            if(start == nextPoint)
                continue;

            if(board[start][nextPoint] == 0 || board[nextPoint][start] == 0)
                return -1;

            result = Math.max(result,board[start][nextPoint] + board[nextPoint][start]);
        }

        return result;
    }
}