[백준/Java] 21940

가운데에서 만나기

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

문제

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

도시를 연결하는 도로는 일방 통행만 있어서 도시 $A_{i}$에서 도시 $B_{i}$로 가는 시간과 도시 $B_{i}$에서 도시 $A_{i}$로 가는 시간이 다를 수 있다.

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

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

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

입력

첫 번째 줄에는 도시의 개수 $N$과 도로의 개수 $M$이 주어진다.

두 번째 줄부터 M + 1줄까지 도시 $A_{i}$, 도시 $B_{i}$, 도시 $A_{i}$에서 도시 $B_{i}$로 이동하는데 걸리는 시간 $T_{i}$가 공백으로 구분되어 주어진다.

$M + 2$줄에는 준형이와 친구들의 총 인원 $K$가 주어진다.

$M + 3$줄에는 준형이와 친구들이 살고 있는 도시의 번호 $C_{i}$가 공백으로 구분되어 주어진다.

출력

위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.

문제 풀이 방법 및 해설

이번 알고리즘은 플로이드 이다. 플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구해주는 알고리즘으로 알려져 있다.

위 문제는 정점마다 제일 값이 큰 친구의 집까지 왕복거리를 저장을 하고, 이 저장된 값 중에 제일 최소값을 반환하면 된다. 제일 최소값이 여러 개 일 수있으니 리스트로 저장을 하고 반환하면 된다!

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        final int max = Integer.MAX_VALUE / 2;
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] map = new int[N+1][N+1];

        for(int i = 1 ; i<= N ;i++){
            Arrays.fill(map[i], max);
            map[i][i] = 0;
        }

        for(int i = 0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            map[a][b] = t;
        }

        for(int i = 1 ; i <= N ; i++){
            for(int j = 1 ; j <= N ; j++){
                for(int k = 1 ; k <= N ; k++){
                    if(map[j][k] > map[j][i] + map[i][k]){
                        map[j][k] = map[j][i] + map[i][k];
                    }
                }
            }
        }

        int K = Integer.parseInt(br.readLine());
        ArrayList<Integer> lst = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < K ; i++){
            lst.add(Integer.parseInt(st.nextToken()));
        }

        int[] answer = new int[N+1];
        for(int i = 1; i <= N ; i++){
            for(int j = 0; j < K ; j++){
                int idx = lst.get(j);
                answer[i] = Math.max(answer[i], map[i][idx] + map[idx][i]);
            }
        }

        lst = new ArrayList<>();
        int minValue = Integer.MAX_VALUE;
        for(int i = 1 ; i <= N ; i++){
            if(minValue > answer[i]){
                minValue = answer[i];
                lst.clear();
                lst.add(i);
            }else if(minValue == answer[i]){
                lst.add(i);
            }
        }
StringBuilder sb = new StringBuilder();
        for(int data : lst){
            sb.append(data + " ");
        }
        System.out.println(sb);
    }
}