[PS] 백준21940 : 가운데에서 만나기(Java)

문제

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

21940번: 가운데에서 만나기

---

풀이

모든 정점으로부터 다른 모든 정점까지의 거리를 구하는 문제로써 플로이드 워셜 풀이가 가능
하지만 나는 데이크스트라로 풀이함

최초 접근

주어지는 K개의 노드를 출발점으로 하여금 데이크스트라를 수행하면서 전역 dp배열에 최대 비용을 기록 후 갈 수 있는 노드들에 대해 탐색하여 왕복시간을 구하려함.

하지만 이렇게 풀이하게 될 경우 왕복시간을 구할수가 없기 때문에 잘못된 풀이.

---

접근법

주어지는 K로부터 모든 노드에 대해 왕복시간을 구하고 모두가 갈 수 있는 노드들 중 최대 왕복시간이 최소가 되는 노드의 번호를 구하는 문제로 데이크스트라로 풀이를 하려면

1. 모든 정점으로부터 데이크스트라를 수행
2. 2차원 dp배열을 전역으로 초기화하여 데이크스트라 로직에 활용
3. 각 정점을 모임장소로 보고 최대 왕복시간을 구한 뒤 최소값 비교를 진행하면서 결과를 우선순위 큐에 추가

우선순위 큐를 추가적으로 사용하는 이유는 최소시간이 같은 노드가 여러개 존재할 시 오름차순으로 출력을 해야하기 때문에 우선순위 큐를 통해 결과를 정렬하기 위함.

최초 접근 시에 K개의 노드가 모두 갈 수 있는 노드를 탐색하려했는데 위와 같이 2차원 dp배열값을 활용하면 갈 수 없는 노드에 대해서는 INF값이 들어있기 때문에 고려하지 않아도 됨.

 

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//BOJ_21940 가운데에서 만나기
public class Main {
    static class Node {
        int v;
        int w;

        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    static int N, M, K;
    static List<List<Node>> list;
    static int[] arr;
    static int[][] dp;
    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()); //도시의 개수
        M = Integer.parseInt(st.nextToken()); //도로의 개수

        list = new ArrayList<>();
        for(int i=0; i<=N; i++) list.add(new ArrayList<>());
        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 weight = Integer.parseInt(st.nextToken());
            list.get(start).add(new Node(end, weight));
        }

        K = Integer.parseInt(br.readLine()); //총 인원
        st = new StringTokenizer(br.readLine());
        arr = new int[K];
        for(int i=0; i<K; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); //출발 정점번호
        }

        dp = new int[N+1][N+1];
        for(int i=0; i<=N; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        //모든 정점으로부터 각 정점까지의 최단경로 구함
        for(int i=1; i<=N; i++) {
            dijkstra(i);
        }

        PriorityQueue<Integer> res = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        //각 정점을 모임장소로 잡고 친구별로 해당 지점까지의 왕복시간을 구한 후
        int distance = Integer.MAX_VALUE;
        for(int i=1; i<=N; i++) {
            int place = i;
            int max = 0;
            for(int friend : arr) {
                int sum = dp[friend][place] + dp[place][friend]; //왕복시간
                max = Math.max(max, sum); //최대 왕복시간
            }

            if(max < distance) { //최대 왕복시간이 현재 최소시간보다 낮을 경우 정답 갱신
                res.clear();
                res.offer(i);
                distance = max;
            }
            else if(max == distance) {
                res.offer(i);
            }
        }

        //인접리스트로 담고
        //dp배열은 2차원으로 해서
        //각 정점으로부터 다른정점들까지의 거리를 구하는데 최대값만 담고
        //마지막에 i->j 로가는거 j->i 로가는거 더해서 최소값 찾고, 값 같은 애들 동시에 다 출력
        while(!res.isEmpty()) {
            System.out.print(res.poll() + " ");
        }
    }

    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.w - o2.w;
            }
        });
        pq.offer(new Node(start, 0));
        dp[start][start] = 0;

        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            if(dp[start][cur.v] < cur.w) continue;

            for(Node n : list.get(cur.v)) {
                int dist = cur.w + n.w;
                if(dp[start][n.v] > dist) {
                    dp[start][n.v] = dist;
                    pq.offer(new Node(n.v, dist));
                }
            }
        }
    }
}

 

 

---

정리

• 지난 소프티어에서 풀지 못했던 문제와 비슷한 유형의 문제인 것 같아서 한번 도전해보았는데 총 2시간 30분 정도 소요한 것 같음….
• 아무래도 모든 정점으로부터 다른 모든정점까지의 거리를 구해야 왕복시간도 동시에 구해지기 때문에 플로이드 워셜 풀이가 편한데 데이크스트라로 풀이하려 했기에 어지러웠다고 생각함
  • 처음 접근할 때 데이크스트라를 K번만큼 돌리면 시간초과가 발생하지 않을까 생각했지만 입력으로 들어오는 노드의 개수가 최대 200개이기 때문에 통과할 수 있었음