https://www.acmicpc.net/problem/1389
문제
> 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.
> 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.
> 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?
> 천민호는 이강호와 같은 학교에 다니는 사이이다.
> 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다.
> 최백준과 김선영은 같이 Startlink를 창업했다.
> 김선영과 김도현은 같은 학교 동아리 소속이다.
> 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다.
> 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.
> 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.
> 오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다.
> 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.
> 예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.
> 1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다.
따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.
> 2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다.
따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.
> 3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다.
따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.
> 4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다.
4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.
> 마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다.
5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.
> 5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.
> BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.접근
입력받은 친구들의 관계로 연결 관계를 이차원벡터로 만든다.
너비우선 탐색을 이용하여 각 번호의 사람마다 탐색을 하여 한 관계를 볼 때마다 1씩 거리를 누적하고 방문처리를 하며 모두 방문처리가 되어 관계확인이 끝났다면, 각각의 사람까지의 관계로 가는데 얼마나 걸렸는지를 벡터에 저장해둔다.
그리고 그 값들을 전부 더해 최종 베이컨수를 구한다.
이제 1번 부터 N번까지 이 저장된 베이컨수를 가지고 두 베이컨 수를 비교해 더 작은 수의 사람의 번호를 저장해가며 제일 작은 사람을 찾는다.
문제해결
> 사람들의 관계도를 저장할 num벡터와 각 사람의 베이컨수를 저장할 bacon벡터를 만든다.
> M번 반복으로 관계를 입력받고 a,b가 친구면 b,a도 친구이므로 양방향으로 num에 저장한다.
> 최종 가장 작은 베이컨수를 가진 사람의번호를 저장할 result변수를 하나 만들고 반복문으로 모든사람의 베이컨수를 따지기 위해 1부터 N까지 돌며 베이컨수를 구하는 메소드인 kevin을 인자로 번호, 누적할 거리로 주고 호출한다.
> Kevin메소드에서는 인자로 들어온 번호와 거리를 가지고 큐에 넣고 시작하며 num에 저장된 관계도를 따라 큐에 모든 번호의 사람이 들어가며 거리가 누적되어 간다.
> 모든 사람의 방문이 끝나면 while문이 깨져 아래의 sum인 총 베이컨수를 구한다.
> rst벡터에는 각 번호의 사람이 인덱스로 얼마의 거리에 있는지 들어있다. 이를 전부 더해주고 반환해준다.
그럼 이 반환값이 각 사람별 베이컨 수 이다.
> N번까지 돌며 각각의 kevin의 반환값이 저장된 bacon[i]을 비교해서 더 작은 값이 나오면 그 i값을 result에 저장하며 결과를 찾고 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int N, M;
int Min = INT_MAX;
vector<vector<int>> num;
vector<bool> visited;
vector<int> bacon;
int kevin(int start, int cnt)
{
vector<int> rst(N+1);
visited.assign(N + 1, false);
queue<pair<int, int>> q;
q.push({ start, cnt });
visited[start] = true;
while (!q.empty())
{
int fn = q.front().first;
int fcnt = q.front().second;
q.pop();
rst[fn] = fcnt;
for (auto a : num[fn])
{
if (!visited[a])
{
q.push({ a, fcnt + 1 });
visited[a] = true;
}
}
}
int sum = 0;
for (int i = 1; i <= N; i++) sum += rst[i];
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
num.resize(N+1, vector<int>());
bacon.resize(N + 1);
while (M--)
{
int a, b;
cin >> a >> b;
num[a].push_back(b);
num[b].push_back(a);
}
int result = 0;
for (int i = 1; i <= N; i++)
{
bacon[i] = kevin(i, 0);
if (Min > bacon[i])
{
Min = bacon[i];
result = i;
}
}
cout << result << '\n';
}
후기
문제이해를 잘못하여 1번사람에 대한 베이컨수만 구하고 1번부터 각각 번호까지 2, 1, 1, 2 인것에서 3번과 4번이 젤 작은데 이중 3번이 더 작은 번호이므로 이를 출력했다.
마침 결과가 같게나와 착각했다.
문제를 다시읽고 해결했다.
