문제 링크: 1389번: 케빈 베이컨의 6단계 법칙
1. 코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::vector<std::vector<int>> userGraph(N + 1);
// 친구 관계 입력
for (int i = 0; i < M; ++i)
{
int u, v;
std::cin >> u >> v;
userGraph[u].push_back(v);
userGraph[v].push_back(u);
}
std::vector<int> distance(N + 1);
std::queue<int> userQueue;
int minSum = N * N;
int ansUser = 0;
for (int user = 1; user <= N; ++user)
{
std::fill(distance.begin() + 1, distance.end(), -1);
distance[user] = 0;
userQueue.push(user);
// BFS로 최단 거리 업데이트
while (!userQueue.empty())
{
int u = userQueue.front();
userQueue.pop();
for (int v : userGraph[u])
{
if (distance[v] == -1)
{
distance[v] = distance[u] + 1;
userQueue.push(v);
}
}
}
int sum = 0;
// 케빈 베이컨의 수 계산
for (int i = 1; i <= N; ++i)
{
sum += distance[i];
}
// 케빈 베이컨의 수가 가장 작은 경우
if (sum < minSum)
{
minSum = sum;
ansUser = user;
}
}
std::cout << ansUser;
return 0;
}
C++
복사
2. 분석
BFS를 활용해 최단 거리를 구하는 것이 핵심인 문제였습니다. 최단 거리를 구하기 위해 userGraph, distance, userQueue를 사용합니다. 유저 A로부터 다른 모든 유저의 최단 거리를 구하려고 할 때 다음과 같이 진행됩니다.
1.
모든 유저의 distance를 -1로 설정합니다.
2.
유저 A의 distance는 0으로 설정하고 userQueue에 유저 A를 넣습니다
3.
BFS 반복문에 진입합니다.
4.
userQueue에서 유저 한 명을 꺼내고, userGraph를 이용해서 꺼낸 유저에 연결된 유저들을 조사합니다.
5.
연결된 유저의 distance가 -1이면 최단 거리를 계산하고, -1이 아니면 최단 거리를 이미 계산한 것으로 간주합니다.
6.
최단 거리를 계산할 때 유저 u → 유저 v라고 하면, 유저 v의 최단 거리를 distance[u] + 1로 계산합니다. 계산 후 유저 v는 큐에 넣습니다.
7.
큐에 유저가 없을 때까지 BFS 반복문이 진행됩니다.
위와 같은 과정으로 최단 거리를 구한 후 케빈 베이컨 수를 계산합니다. 가장 작은 케빈 베이컨 수라면 정답에 해당하는 유저를 업데이트합니다. 시간 복잡도를 계산하겠습니다. 유저 한 명의 케빈 베이컨 수를 계산할 때 userGraph에 BFS를 수행합니다. BFS를 수행하면, 모든 정점을 한 번씩 방문하고 방문 시 연결된 간선을 순회합니다. 따라서 유저 한 명의 케빈 베이컨 수를 구할 때 시간 복잡도는 O(N + M)입니다. 모든 유저의 케빈 베이컨 수를 구하기 때문에 모든 유저에 대해 BFS를 수행합니다. 이것까지 고려하면 최종 시간복잡도는 O(N * (N + M))입니다.