[ 백준 / 1389 ] 케빈 베이컨의 6단계 법칙 (C++)

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

 

난이도 : 실버 1 
알고리즘 유형 : 그래프탐색, BFS
풀이 시간 : 26분 

문제 풀이 

문제를 간략히 요약하자면, "한 사람이 모든 사람을 만나는 데 걸리는 비용이 가장 적은 사람을 찾아라"이다.

정점 N의 범위가 작았고(N ≤ 100), 모든 사람의 경우를 구해야 하기 때문에 BFS를 사용하여 값을 구한 뒤, 최솟값을 비교하면 될 것이라고 생각하였다.

최솟값 비교의 경우, BFS를 진행하며 방문한 다른 정점과의 거리를 모두 더한 뒤 거리의 합을 비교하는 방식을 사용하였다.

 

위 문제를 풀며, 효율성을 높이기 위해 다음과 같은 방법을 사용하였다.

1. 정점의 합을 계산해 주는 과정에서 이전에 계산된 정점의 합보다 커지게 된다면, 그대로 함수를 종료하도록 하였다.
2. 문제의 요구조건에서 "최소 거리인 정점이 2개 이상일 경우, 정점이 작은 녀석을 출력하라"라고 하였기 때문에, 정점을 순차적으로 탐색하되, 무조건 현재 거리의 합이 최대 거리의 합보다 작은 경우에만 정점을 업데이트하였다.

추가로 그래프를 생성할 때, 인접 리스트가 아닌 인접 행렬을 사용하였다. 이러한 이유는 주어진 입력에 "정점 - 간선 정보가 중복하여 들어올 수도 있다"라고 하여 중복값 처리에 번거롭지 않기 위해 사용하였다.

 

다음 순서로 풀이를 진행하였다.

1. 양방향 그래프 생성
2. 1번 정점부터 N번 정점까지 순회하며 BFS 진행
   • 모든 정점을 방문하기 위한 거리를 계산
   • 만약 현재 거리의 합이 이전 거리의 최댓값보다 짧다면, 케빈 베이컨 정점 업데이트

 

코드

/*
1389. 케빈 베이컨의 6단계 법칙

임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임
단계의 총 합이 가장 적은 사람

케빈 베이컨의 수가 가장 작은 사람을 구하자

풀이:
한 녀석이 모든 정점에 도달하는 데 걸리는 가중치의 총 합을 구하는 문제
M <= 5000, n <= 100

1. 중복 입력의 경우가 있기 때문에, 모든 사람 정보를 2차원 배열 형식으로 저장
2. 입력에서 모든 친구는 연결되어있다. 
3. bfs 탐색 진행
정답 출력의 경우 가장 작은 수의 사람을 업데이트 하는 방식으로 진행
*/

#include <iostream>
#include <queue>
#include <cstring>
#define INIT cin.tie(0); ios::sync_with_stdio(false);

using namespace std;

int n, m;
int s, e;
int relationship[101][101] = { 0, };
int visited[101] = { 0, };

int ans = 0;
int max_r = 1000000;

void bfs(int su) {
	queue<int> q;
	memset(visited, 0, 101 * sizeof(int));
	q.push(su);
	visited[su] = 1;
	int tmp_r = 0;

	while (!q.empty()) {
		int u = q.front();
		q.pop();

		tmp_r += visited[u] - 1;
		if (tmp_r >= max_r)
			return;

		for (int v = 1; v <= n; v++) {
			if (relationship[u][v] && !visited[v]) {
				visited[v] = visited[u] + 1;
				q.push(v);
			}
		}
	}

	// 케빈 베이컨 수 계산
	if (tmp_r < max_r) {
		ans = su;
		max_r = tmp_r;
	}
}

int main() {
	INIT;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> s >> e;
		relationship[s][e] = 1;
		relationship[e][s] = 1;
	}

	// 1번부터 순회하며 bfs 진행
	for (int i = 1; i < n + 1; i++) {
		bfs(i);
	}

	cout << ans << '\n';

	return 0;
}

배운 점 

BFS/DFS 진행 시 방문 배열(visited)을 초기화하기 위해 줄곧 `memset()` 함수를 사용하였다. 하지만 백준에서 memset 사용 시 컴파일 에러가 발생하기에 궁금하여 찾아보았더니, 백준 사이트에서는 "GNU C/C++" 컴파일러를 사용하기 때문에 `#include <cstring>` 헤더를 사용해야 한다고 했다.

이런 알고리즘 외적인 부분을 알아가는 건 너무 재밌는 것 같다 ~ 숙지하자 !!