백준_케빈 베이컨의 6단계 법칙

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

[ 나의 해결법 ]

다익스트라 알고리즘을 이용해서 문제를 풀었다. 사람1을 시작해서 다익스트라 알고리즘을 진행하면, 사람1과 다른 사람들과의 최단거리를 배열 dist에 구할 수 있다. 배열 dist의 모든 원소를 더하면 사람1의 케빈 베이컨의 값이 나온다.

이런 식으로 사람1부터 N명까지 진행하면서 케빈 베이컨 값이 최소의 유저를 찾으면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include <iostream> #include <vector> #include <queue>   #define MAX 101 #define INF 99999999   using namespace std;   int N, M; vector<pair<int, int>> adj[MAX];   void InData() {     cin >> N >> M;     for (int i = 0; i < M; i++)     {         int src, dst;         cin >> src >> dst;         adj[src].push_back(make_pair(dst, 1));         adj[dst].push_back(make_pair(src, 1));     } }   int Dikstra(int node) {     priority_queue<pair<int, int>> pq;     vector<int> dist(MAX, INF);       dist[node] = 0;     pq.push(make_pair(0,node));       while (!pq.empty())     {         int min_dist = -pq.top().first;         int min_node = pq.top().second;         pq.pop();           for (int v = 0; v < adj[min_node].size(); v++)         {             int next_node = adj[min_node][v].first;             int next_dist = min_dist + adj[min_node][v].second;             if (next_dist < dist[next_node]) {                 dist[next_node] = next_dist;                 pq.push(make_pair(-next_dist, next_node));             }         }     }       int ret = 0;     for (int i = 1; i <= N; i++)         ret += dist[i];     return ret; }   int main() {     int kevin;     int min_kevin = INF, min_node;       InData();       for (int v = 1; v <= N; v++)     {         kevin = Dikstra(v);         if (kevin < min_kevin)         {             min_kevin = kevin;             min_node = v;         }     }       cout << min_node << endl;     return 0; }