백준 13424 - 비밀 모임

문제

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

리뷰

플로이드 워셜 혹은 다익스트라로 풀이할 수 있는 간단한 문제였다.
필자는 플로이드 워셜이 더 풀이가 간단히 나올듯 하여 플로이드 워셜을 이용해
로직을 구성하였다.

전체 방중 $K$명의 친구가 모이기에 가장 가까운 방을 구하는 것이 답이었다.
따라서 플로이드 워셜을 통해 모든 방간 최단 경로 비용을 구하고, $N$개의 방중
한 방인 $i$까지 $K$명의 친구가 도달하기 위한 비용의 합을 구하여, 비용 합이 가장
최소로 도출되는 방을 구하였다.

로직의 시간복잡도는 플로이드 워셜의 $O(N^3)$으로 수렴하고 $N=100$인 최악의
경우에도 무난히 제한 조건 1초를 통과한다.

초반에 map의 초기값을 MAX_VALUE 로 할당했다보니 플로이드 워셜 로직내에서
갱신시 오버플로우를 방지하기 위하여 조건문을 설정했는데, 이 부분에서 실수가 있어
불필요하게 헤멨다..

코드

import static java.lang.Integer.*;

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

public class Main {
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = parseInt(st.nextToken());
            int M = parseInt(st.nextToken());

            map = new int[N + 1][N + 1];
            initMap(N);

            int a, b, c;
            while (M-- > 0) {
                st = new StringTokenizer(br.readLine());
                a = parseInt(st.nextToken());
                b = parseInt(st.nextToken());
                c = parseInt(st.nextToken());

                map[a][b] = map[b][a] = c;
            }

            floyd(N);

            int K = parseInt(br.readLine());
            List<Integer> rooms = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            while (K-- > 0) {
                int room = parseInt(st.nextToken());
                rooms.add(room);
            }

            int minRoom = 0;
            int minSum = MAX_VALUE;
            for (int i = 1; i <= N; i++) {
                int sum = 0;

                for (Integer room : rooms) {
                    sum += map[room][i];
                }

                if (sum >= minSum) {
                    continue;
                }

                minRoom = i;
                minSum = sum;
            }

            sb.append(minRoom).append("\n");
        }

        System.out.print(sb);
        br.close();
    }

    static void initMap(int N) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    continue;
                }

                map[i][j] = MAX_VALUE;
            }
        }
    }


    static void floyd(int N) {
        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] == MAX_VALUE || map[k][j] == MAX_VALUE) {
                        continue;
                    }

                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }
    }
}

결과