[백준OJ] 13424번 비밀 모임

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

13424번: 비밀 모임

---

 

-풀이-

플로이드-와샬 알고리즘을 이용하여 모든방에서 모든방까지의 최단거리를 구해주었다.

그런뒤, 친구들이 있는 방의 위치를 입력받았다.

그런뒤 1번방~N번방까지 각각의 방을 기준으로 모든 친구들까지의 거리를 플로이드-와샬 알고리즘을 이용하여 구한 최단거리를 이용하여 가장 짧은 거리들의 합을 구해준 뒤, 가장 작은 거리와 그 방을 갱신시켜주면 된다.

 

-시간복잡도-

플로이드-와샬 알고리즘의 시간복잡도는 O(N³)이 된다.

각 방을 기준으로 모든 친구들까지의 거리의 합을 구해서 최소가 되는 방을 구하는 알고리즘은 O(NK)가 된다.

따라서 시간복잡도는 O(N³)가 된다.

 

-코드-

#include <algorithm>
#include<iostream>
#include<vector>
#define INF 987654321
using namespace std;

long long maze[101][101]={0};
int N,M,K,T;

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    cin>>T;
    while(T--){
        vector<int> friends;
        cin>>N>>M;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                maze[i][j]=INF;
            }
        }
        for(int i=0;i<M;i++){
            int a,b,c;
            cin>>a>>b>>c;
            maze[a][b]=c;
            maze[b][a]=c;
        }
        for(int k=1;k<=N;k++){
            for(int i=1;i<=N;i++){
                for(int j=1;j<=N;j++){
                    if(i==j||j==k||i==k) continue;
                    maze[i][j]=min(maze[i][j],maze[i][k]+maze[k][j]);
                }
            }
        }
        cin>>K;
        for(int i=0;i<K;i++){
            int data;
            cin>>data;
            friends.push_back(data);
        }
        long long min_dist=INF;
        int room=-1;
        for(int i=1;i<=N;i++){
            long long sum=0;
            for(int j=0;j<K;j++){
                if(maze[i][friends[j]]!=INF){
                    sum+=maze[i][friends[j]];   
                }
            }
            if(min_dist>sum){
                min_dist=sum;
                room=i;
            }
        }
        cout<<room<<"\n";
    }
    
   
}