[백준]29140: 가운데에서 만나기 - JAVA

[백준]29140: 가운데에서 만나기

21940번: 가운데에서 만나기

풀이

🪑 생각지도 못한 부분에서 헤멨던 문제였다..! 일단 문제를 보자마자 Shortest Path 문제라는 것을 알았고 다익스트라, 플로이드-와샬 알고리즘을 떠올렸다.

 

 

📝문제의 조건을 정리해 보자!

• 도시와 도시를 연결하는 간선은 유향(방향성을 가진다)이다.
• 왕복 시간은 A -> B -> A이다.
• 왕복 시간 중 최대가 최소가 되는 도시를 선택한다.
• 여러개인 경우 오름차순으로 출력한다.

 

 

🙋‍♀️ '최대가 최소'에서 이분탐색 힌트를 얻고 처음에는 이분탐색으로 접근하였다.

• 도시별로 왕복 시간을 모두 계산해준 다음, 기준값을 왕복 시간으로 정해준다.
• mid 시간으로 친구들이 살고있는 도시에서 이동할 수 있는 도시가 있는지 확인하며 list를 작성해 주었다.
• 이동할 수 있는 공통된 도시가 존재하면 더 작은시간, 없으면 더 큰시간을 탐색하도록 하였다.
• 일단 이 방법으로 구현하면서 왕복 시간을 계산해 줘야 하는 점과, 이분탐색으로 하나 이상 도달할 수 있는 도시가 있는지 확인하면서 동시에 해당 도시가 조건에 맞는 도시인 X가 될 수 있는지 확인해 주어야 했다.
• 굉장히 복잡하고 불필요한 연산도 많이 포함되었다. 과감히 이분탐색을 버리고 다시 쉽게 생각해 보았다.

 

 

🔧 다시 문제의 조건을 따라 풀이 순서를 간략하게 정리해 보자!

1. 도시와 도시를 연결하는 최단거리를 구해준다.
2. 구한 최단거리를 사용하여 왕복시간 중 최대 값을 찾아준다.
3. 최대값 중에서 최소값을 찾아준다.
4. 최소값으로 도달할 수 있는 도시를 찾아준다.
5. 도시를 오름차순으로 출력한다.

 

🔹 도시와 도시를 연결하는 최단거리를 구해준다.

- 대표적인 Shortest Path 알고리즘으로는 다익스트라, 플로이드-와샬이 있다.

- 일반적으로 다익스트라는 한 정점에서 모든 정점으로 가는 최단거리를 구할때 사용하고, 플로이드-와샬은 모든 정점에서 모든 정점으로 가는 최단거리를 구할 때 사용한다.

- 이 문제에서는 모든 정점에서 모든 정점으로 가는 최단거리를 구하므로 플로이드-와샬을 사용해 주었다. 물론 다익스트라를 여러번 반복해서 구현해 주어도 된다.

- 단, 주의할 점은 플로이드-와샬은 2차원 배열을 사용해야 하므로 메모리 제한을 확인하고 사용해 주어야 한다. 

 

🔹 구한 최단거리를 사용하여 왕복시간 중 최대값을 찾아준다.

- 플로이드-와샬로 모든 정점간의 최단 거리를 구해주었으니 왕복 시간을 계산하는건 어렵지 않다.

- 도시별로 왕복 시간 중에서 최대값을 찾아 배열로 저장해 주었다.

 

🔹 최대값 중에서 최소값을 찾아준다.

- 이 문제에서 원하는 정보는 왕복시간들 중 최대가 최소인 값이다.

- 그러므로 최대값들 중에서 최소값을 찾아준다.

 

🔹 최소값으로 도달할 수 있는 도시를 찾아준다.

- 최소값으로 도달할 수 있는 도시는 왕복 거리의 최대값이 최소값보다 작거나 같은 도시들이다.

- 해당되는 도시들을 list에 담아주었다.

 

🔹 도시를 오름차순으로 출력한다.

- list에 담긴 결과를 오름차순 정렬하여 출력한다. 

 

코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        //입력
        int n = scan.nextInt();
        int m = scan.nextInt();
        int INF = n * m + 1;
 
        int[][] dist = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dist[i][j] = INF;
            }
            dist[i][i] = 0;
        }
 
        for(int i = 0; i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int c = scan.nextInt();
            if(dist[s][e] > c) dist[s][e] = c;
        }
        
        int k = scan.nextInt();
        ArrayList<Integer> city = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            city.add(scan.nextInt());
        }
        //입력 끝
 
        //플로이드와샬
        for(int l = 1; l <= n; l++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(dist[i][j] > dist[i][l] + dist[l][j]) dist[i][j] = dist[i][l] + dist[l][j];
                }
            }
        }
 
        int[] max = new int[n + 1];
        int min = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < city.size(); j++) {
                max[i] = Math.max(max[i], dist[city.get(j)][i] + dist[i][city.get(j)]);
            }
            min = Math.min(min, max[i]);
        }
 
        //최소값으로 갈 수 있는 도시 찾음.
        ArrayList<Integer> result = new ArrayList<>();
        for(int i = 1; i <= n; i++) {
            if(min >= max[i]) result.add(i);
        }
        Collections.sort(result);
 
        StringBuilder sb = new StringBuilder();
        for(int c : result) {
            sb.append(c + " ");
        }
        System.out.println(sb.toString());
    }
}