[JAVA] 백준 21940번 : 가운데에서 만나기

[21940번 : 가운데에서 만나기] - Gold4

 

---

[ 문제 ]

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

 

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

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

 

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

 

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

---

[ 입력 ]

• 첫 번째 줄에는 도시의 개수 N과 도로의 개수 M이 주어진다.
• 두 번째 줄부터 M + 1줄까지 도시 Ai, 도시 Bi, 도시 Ai에서 도시 Bi로 이동하는데 걸리는 시간 Ti가 공백으로 구분되어 주어진다.
• M + 2줄에는 준형이와 친구들의 총 인원 K가 주어진다
• M + 3줄에는 준형이와 친구들이 살고 있는 도시의 번호 Ci가 공백으로 구분되어 주어진다.

---

[ 출력 ]

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

[ # 예제 입력 1 ]
4 9
1 2 9
2 3 9
3 1 9
1 4 1
4 1 1
2 4 1
4 2 1
3 4 1
4 3 1
3
1 2 3

[ # 예제 출력 1 ]
4


[ # 예제 입력 2 ]
3 3
1 2 1
2 3 1
3 1 1
2
1 2

[ # 예제 출력 1 ]
1 2 3

---

[ Code ]

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

public class Main {
    static class Node implements Comparator<Node> {
        int place, cost;

        public Node(int place, int cost) {
            this.place = place;
            this.cost = cost;
        }

        @Override
        public int compare(Node o1, Node o2) {
            return o1.place - o2.place;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] map = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(map[i], Integer.MAX_VALUE);
            map[i][i] = 0;
            map[i][0] = 0;
        }

        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 cost = Integer.parseInt(st.nextToken());
            map[start][end] = cost;
        }

        int peopleCnt = Integer.parseInt(br.readLine());
        int[] people = new int[peopleCnt];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < peopleCnt; i++) {
            people[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 (map[i][k] != Integer.MAX_VALUE && map[k][j] != Integer.MAX_VALUE) {
                        map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                    }
                }
            }
        }

        List<Node> result = new ArrayList<>();
        int point = 0, min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            int max = 0;
            for (int j = 0; j < peopleCnt; j++) {
                max = Math.max(max, map[i][people[j]] + map[people[j]][i]);
            }

            if (min > max) {
                result = new ArrayList<>();
                min = max;
                point = i;
                result.add(new Node(point, min));
            } else if (min == max) {
                result.add(new Node(i, min));
            }
        }

        if (result.size() > 1) {
            for (Node cur : result) {
                bw.write(cur.place + " ");
            }
        } else {
            bw.write(String.valueOf(point));
        }
        bw.close();
    }
}

 

• 구하고자 하는 것 : 정점 A에 대하여 준형이와 친구들 중 가장 최댓값을 구한다.
• ex. 정점 1 
  • 준형 : 1번 정점에 위치 (1 -> 1로 이동 + 1 -> 1로 이동 = 0 + 0)
  • 친구 : 2번 정점에 위치 (1 -> 2로 이동 + 2 -> 1로 이동 = a + b)
  • 최댓값 : Math.max(0, a+b) -> a+b
• 정점 N까지 모두 최댓값을 구한 후 `그 중에서도 가장 최솟값인 정점`을 출력한다.
• (문제가 너무 모호하다...................)

 

• map이라는 배열을 만들어 각 정점에서 다른 정점으로 향하는 거리를 담는다.
• 플로이드 워셜을 이용하여 각 정점마다 다른 정점으로 향하는 최단 거리를 구한다.
• 정점 N에서 준형이와 친구들이 위치한 정점까지 왕복 거리의 최댓값을 구한다.
• `min` 값보다 왕복거리가 작다면 result 리스트를 초기화한 후 리스트에 추가한다.
• `min` 값과 값이 같다면 초기화하지 않고 값을 추가한다.
• result 리스트에 담긴 값이 여러 개라면 사이에 공백을 추가로 출력하고, 값이 하나라면 바로 출력한다.