[BOJ13424] 비밀 모임 (플로이드 워셜, 최단 경로)

 

 

 

---

문제 링크

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

13424번: 비밀 모임

 

문제 풀이 

- 플로이드 워셜 기본 문제

- 시간 복잡도

= 플로이드 워셜 수행 + 친구 별 방에 대한 최단 거리 합산 + 최소 비용 가지는 방 번호 구하기 

= O(N^3) + (N^2) + (N)       (최대 친구 수는 N 이하, N번 방)

 

절차

1) 각 노드별 다른 노드에 대한 최단 경로를 플로이드 워셜 알고리즘으로 구한다, 시간 복잡도 O(N^3)

2) 친구별 방에 대한 최단 거리 비용을 각각 합산한다. 

3) 최단 거리를 가지는 방의 번호를 구한다

 

 

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int T;

    static int N, M, K;

    static int[][] floyd;

    static int INF = 100001;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        while(T > 0) {
            T -= 1;
			
            // 1. 입력 처리
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 방의 개수 (노드)
            M = Integer.parseInt(st.nextToken()); // 비밀 통로의 개수 (간선)

            floyd = new int[N + 1][N + 1];
            for(int i = 1; i <= N; i++) {
                Arrays.fill(floyd[i], INF);
                floyd[i][i] = 0;
            }

            for(int i = 1; i <= M; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                floyd[from][to] = cost;
                floyd[to][from] = cost;
            }

            // 2. 플로이드 워셜 수행
            pro();
            

            // 3. 친구별 방에 대한 비용 합산
            K = Integer.parseInt(br.readLine()); // 친구의 수
            st = new StringTokenizer(br.readLine());
            int[] result = new int[N + 1];
            for(int i = 1; i <= K; i++) {
                int friend = Integer.parseInt(st.nextToken());

                for(int j = 1; j <= N; j++) {
                    result[j] += floyd[friend][j];
                }
            }

            // 4. 최소 비용가지는 방 번호 구하기
            int ans = Integer.MAX_VALUE;
            int cost = Integer.MAX_VALUE;
            for(int i = 1; i <= N; i++) {
                if(result[i] < cost) {
                    ans = i;
                    cost = result[i];
                }
            }

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

        System.out.println(sb.toString());
    }

    static void pro() {
        for(int k = 1; k <= N; k++) {
            for(int i = 1; i <= N; i++) {
                for(int j = 1; j <= N; j++) {
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        input();
    }
    
}