백준 - 13424 비밀 모임(JAVA)

문제 링크

---

풀이

플로이드 와샬 알고리즘을 이용하여 모든 정점의 최소 거리를 갱신해둔 후, 1~n까지 반복문을 돌린다. 반복문의 i를 시작지점으로 잡고 해당 시작점과 모든 친구들의 위치까지 최단거리의 총합을 계산하여 가장 적은 합계가 나오는 지점을 출력한다.

주의할 점

• 가장 적은 합계가 나오는 지점, 즉 정답이 여러 개인 경우 번호가 가장 작은 방 번호를 출력해야 한다.

---

코드

import java.util.*;

public class Main {

    static final int INF = 987654321;
    static Scanner scan = new Scanner(System.in);
    static int t, n, m, a, b, c, k, ans, min;
    static int[][] dist = new int[101][101];
    static Vector<Integer> v = new Vector<>(); // 친구들이 있는 곳

    static void input() {
        n = scan.nextInt();
        m = scan.nextInt();

        init_dist();

        for (int i = 0; i < m; i++) {
            a = scan.nextInt();
            b = scan.nextInt();
            c = scan.nextInt();
            dist[a][b] = dist[b][a] = c;
        }

        k = scan.nextInt();

        v.clear();
        for (int i = 0; i < k; i++) {
            int pos = scan.nextInt();
            v.add(pos);
        }

        min = INF;
    }

    static void solve() {

        floydwarshall();

        for(int i=1;i<=n;i++){
            int tmp = 0;
            for(int j : v){
                tmp += dist[i][j];
            }
            if(min > tmp){
                min = tmp;
                ans = i;
            }
        }

        System.out.println(ans);
    }

    static void init_dist() {
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                if (i == j) dist[i][j] = 0;
                else dist[i][j] = dist[j][i] = INF;
            }
        }
    }

    static void floydwarshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j) continue;
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }


    public static void main(String[] args) {

        t = scan.nextInt();
        while (t-- > 0) {

            input();
            solve();

        }
    }
}

결론

다익스트라를 사용해도 되지만 이번 문제의 경우 n의 범위가 작았기 때문에 플로이드 와샬 알고리즘을 이용하여 O(n^3)의 시간 복잡도로도 풀이가 가능한 문제였다.