백준 1389

ALGORITHM
2025-09-01

케빈 베이컨의 6단계 법칙

관련 개념

#BFS #그래프 이론

문제

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

📌 1 단계 : 문제 분석하기

  • 이 문제는 그래프를 이용해서 푸는 것이 너무 명백했다.
  • 각 데이터를 노드로 표현 할 수 있고, 각 노드간의 관계를 간선으로 표현 할 수 있다.

📌 2 단계 : 손으로 풀어보기

  • 우선, vector<vector<int>> 자료구조를 활용해서 각 노드에 대한 정보를 입력 받는다.
  • 이후, 1번 인덱스부터 시작하면서, 본인을 제외한 다른 노드간의 거리를 BFS를 통해서 찾는다.
  • 상세한 구현은 아래 코드를 참고하자.

📌 3 단계 : 슈도 코드 작성하기

  • 생략

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <numeric>
#include <algorithm>
#include <set>
 
using namespace std;
 
int main() {
	int N, M;
	int ans = INT_MAX;
	int index = 0;
 
	cin >> N >> M;
 
	vector<vector<int>> user_list(N + 1, vector<int>());
	vector<bool> visited(N + 1, false);
 
	for (int i = 0; i < M; i++) {
		int input1, input2;
		cin >> input1 >> input2;
		user_list[input1].push_back(input2);
		user_list[input2].push_back(input1);
	}
 
	// 각 유저의 케빈 베이컨 수 계산
	for (int i = 1; i <= N; i++) {
		int sum = 0;
		for (int j = 1; j <= N; j++) {
 
			// 본인이면 스킵
			if (i == j) continue;
 
			queue<pair<int, int>> q;
 
			// 근처 유저 넣기
			for (auto& user : user_list[i]) {
				q.push({ user, 1 });
				visited[user] = true;
			}
 
			while (!q.empty()) {
 
				int user = q.front().first;
				int number = q.front().second;
				q.pop();
				
				// 해당 유저를 찾았다면
				if (user == j) {
					sum += number;
					break;
				}
				else {
					for (auto& user : user_list[user]) {
						if (!visited[user]) {
							q.push({ user, number + 1 });
							visited[user] = true;
						}
					}
				}
			}
 
			// 큐 및 배열 초기화
			while (!q.empty()) {
				q.pop();
			}
 
			for (int k = 1; k <= N; k++) {
				visited[k] = false;
			}
 
		}
 
		if (ans > sum) {
			ans = sum;
			index = i;
		}
 
	}
 
	cout << index;
}

📌 5 단계 : 배운점

  • 하지만 이 코드는 BFS를 너무 쓸데없이 많이 돈다는 단점이 있었다.
  • 동적 계획법을 활용하여 반복되는 계산은 최소화 하려면 아래와 같이 할 수 있다.
  • 또한 이 문제는 워샬-플루이드 알고리즘을 사용 할 수 도 있다.
  • 그리고 이번에 배운점은 BFS를 활용 할 때, distance_list[user] = distance + 1; 와 같은 방문 배열 업데이트를 바로 해야지 해당 노드가 중복해서 안들어간다.
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <numeric>
#include <algorithm>
#include <set>
 
using namespace std;
 
int main() {
	int N, M;
	int ans = INT_MAX;
	int index = 0;
 
	cin >> N >> M;
 
	vector<vector<int>> user_list(N + 1, vector<int>());
	vector<int> distance_list(N + 1, 0);
 
	for (int i = 0; i < M; i++) {
		int input1, input2;
		cin >> input1 >> input2;
		user_list[input1].push_back(input2);
		user_list[input2].push_back(input1);
	}
 
	// 각 유저의 케빈 베이컨 수 계산
	for (int i = 1; i <= N; i++) {
 
		int sum = 0;
		
		//BFS 시작
		queue<pair<int, int>> q;
 
		q.push({ i, 1 });
 
		while (!q.empty()) {
			int current = q.front().first;
			int distance = q.front().second;
			q.pop();
 
			for (auto& user : user_list[current]) {
				// 본인 노드 X, 방문한 노드X
				if (distance_list[user] == 0 && i != user) {
					q.push({ user, distance + 1 });
					// 여기 주의! 시점 주의!
					distance_list[user] = distance + 1;
				}
			}
		}
 
		for (auto& distance : distance_list) {
			sum += distance;
		}
 
		if (ans > sum) {
			ans = sum;
			index = i;
		}
 
		// 벡터 초기화
		fill(distance_list.begin(), distance_list.end(), 0);
 
	}
 
	cout << index;
}