케빈 베이컨의 6단계 법칙

#include <iostream>

using namespace std;

// 친구 관계도

int arr[101][101];

// 갈수 잇는 거리

int f[101];

// 방문 노드

int ch[101];

// N 유저의 수 , M 친구관계수

int N, M;

void sol(int i , int cnt)

{

cnt++;

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

{

if (arr[i][j] == 1  && cnt < f[j] && i != j)

{

f[j] = cnt;

ch[j] = 1;

sol(j, cnt);

}

}

}

int main()

{

int min = 9999;

int a, b;

int number=102;

int sum;

cin >> N >> M;

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

{

cin >> a >> b;

arr[a-1][b-1] = 1;

arr[b-1][a-1] = 1;

}

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

{

for (int j = 0; j < N; j++) {

f[j] = 100;

ch[j] = 0;

}

sum = 0;

f[i] = 0;

ch[i] = 0;

sol(i,0);

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

sum += f[j];

if (sum<=min) {

if (min == sum && (i + 1) > number)

continue;

else

{

min = sum;

number = i + 1;

}

}

}

cout << number;

return 0;

}