[백준 1389]케빈 베이컨의 6단계 법칙

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

1)문제 분류 

-BFS

-DFS

-플로라이드 와샬 알고리즘 

2)문제 해결 

- Vector에 연결되어 있는 각 정점을 넣어서 연결고리를 만든다. 

- 각 BOG 유저의 케인베이컨의 수의 합을 알아야하기 때문에, 

   각 Bog유저마다, BFS를 돌려 케빈베이컨 수가 제일 적은 것을 선택한다. 

//12시 5분 ~12시 30분

#include<iostream>

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

int N, M;

vector<int>vt[102];

typedef struct Data

{

int x, cnt;

}Data;

int bfs(int start,int end)

{

bool chk[102][102] = { 0, };

queue<Data>pq;

pq.push({ start,0 });

while (!pq.empty())

{

Data output = pq.front();

pq.pop();

if (output.x == end)

{

return output.cnt;

}

for (int i = 0; i < vt[output.x].size(); i++)

{

if (chk[output.x][vt[output.x][i]] == false)

{

chk[output.x][vt[output.x][i]] = true;

pq.push({ vt[output.x][i] ,output.cnt + 1 });

}

}

}

}

int main()

{

scanf("%d %d", &N, &M);

int x, y;

for (int i = 0; i < M; i++)

{

scanf("%d %d", &x, &y);

vt[x].push_back(y);

vt[y].push_back(x);

}

int ans = 987654321;

int idx = 0;

for (int i = 1; i <= N; i++)

{

int sum = 0;

for (int j = 1; j <= N; j++)

{

if (i != j)

sum+=bfs(i, j);

}

if (sum < ans)

{

ans = sum;

idx = i;

}

}

printf("%d\n", idx);

}