https://www.acmicpc.net/problem/1389
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻
www.acmicpc.net
이 문제의 경우 쉬운 전형적인 bfs문제이다. 모든 정점을 시작점으로 bfs를 돌린다 그 후 정점을 시작점으로 돌리는 케이스마다의 각 정점의 layer의 합을 저장한 후 이를 비교하여 최솟값을 갖는 정점의 값을 출력해 주면 되는 문제였다
bfs의 기본적이 풀이 로직은 이 블로그의 다른글들에 있다. 코드는 아래와 같다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M;
vector<int> bfsv[101];
int arr[101] = { 0, };
int main() {
queue<pair<int, int>> bfsq;
cin >> N >> M;
for (int i = 0; i < M; i++) {
int temp1, temp2;
cin >> temp1 >> temp2;
bfsv[temp1].push_back(temp2);
bfsv[temp2].push_back(temp1);
}
for (int i = 1; i <= N; i++) {
int start = i;
bfsq.push({ start,0 });
bool isVisited[101] = { 0, };
while (!bfsq.empty()) {
int front = bfsq.front().first;
int second = bfsq.front().second;
arr[front] += second;
isVisited[front] = true;
bfsq.pop();
for (int j = 0; j < bfsv[front].size(); j++) {
if (!isVisited[bfsv[front][j]]) {
bfsq.push({ bfsv[front][j], second + 1 });
isVisited[bfsv[front][j]] = true;
}
}
}
}
int min=5001;
int ans = 0;
for (int i = 1; i <= N; i++) {
if (min > arr[i]) {
ans = i;
min = arr[i];
}
}
cout << ans;
}