[백준 1398] 케빈 베이컨의 6단계 법칙

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

1389번: 케빈 베이컨의 6단계 법칙

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <list>

int N, M;			// 유저의 수, 친구 관계의 수
int chk[100 + 10];	//유저 최대 100명

struct _st
{
	int n;
	int cnt;
};

std::queue<_st> Q;	// 현재 유저로부터 각 유저까지의 단계 수 담을 큐
std::list<int>	adj[100 + 10];	// 인접리스트


void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int u = 0; int v = 0;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

}


void BFS(int num)
{
	Q.push({ num, 0 });
	chk[num] = 0;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int nn : adj[data.n]) {
			if (chk[nn] != -1) continue;	// 이미 단계 수를 계산함
			int ncnt = data.cnt + 1;		
			chk[nn] = ncnt;					// data.n 부터 nn까지의 최단거리 계산하여 chk배열 갱신
			Q.push({ nn, ncnt });
		}
	}
}


int get_kb(void)
{
	int res = 0;
	for (int i = 1; i <= N; i++) {
		res += chk[i];
	}
	return res;
}


void get_least_kb(void)
{
	int min = 0x7fffffff;
	int idx = -1;
	
	for (int s = 1; s <= N; s++) {
		memset(chk + 1, 0xff, sizeof(chk[0]) * N);
		BFS(s);
		int tmp = get_kb();
		if (tmp < min) {
			min = tmp;
			idx = s;
		}
	}
	printf("%d", idx);
}



int main()
{
	input();
	get_least_kb();
	return 0;
}

 

이 문제는 "각 유저 간 최단거리를 찾는 문제"이므로 BFS로 해결할 수 있다. 

다만 최단거리를 찾는 것에서 끝나는 것이 아니라, 예컨대 1번 유저에 대하여 2번부터 N번 유저까지의 최단 거리를 각각 구하고, 이를 더하여 '케빈 베이컨 수'를 구해야 한다. 또한 이렇게 구한 케빈 베이컨의 수 중 가장 작은 값을 갖는 유저를 출력해 주어야 했다. 요구사항 더럽게 많다.. 

 

물론 각 노드 사이의 연결 관계를 인접 행렬로 구현할 수 있지만, 이 경우 1번부터 N번 유저까지 연결여부에 관계 없이 무조건 모두 탐색해야 하기 때문에 효율적이지 않다. 그래서 인접리스트로 구현해보았다. 

이를 위해 #include <list>를 통해 각 유저에 연결되어 있는 유저를 저장하였다. 

큐는 현재 탐색하고 있는 유저와, 기준 유저로부터 해당 유저까지의 최단 거리를 저장하기 위해 사용했다. 

이때 chk 배열은 예컨대 1번 유저에 대하여 1번부터 N번까지의 최단 경로를 저장해 놓기 위해 선언했다. 

 

 

// input( ) 함수

인접리스트를 만들기 위해 u와 v를 받으면서 저장해주었다. 

이때 주의해야 할 점은 u와 v가 친구관계이면 v와 u도 친구관계라는 것이다. 따라서 두 노드 모두에 대하여 push_back해주어야 한다. 

 

 

// BFS( ) 함수

각 유저에 대하여 1번부터 N번까지의 유저가 친구인지 여부에 따라 chk 배열을 갱신해준다. 

이때 chk[nn] != -1 일 때 continue 해준 이유는, data.n 유저와 연결된 nn 유저에 대하여 이미 최단거리를 갱신해주었기 때문이다. 최초로 갱신한 값이 최소한의 거리일 것이기 때문에 또 다시 갱신해주지 않는다. 

그렇지 않으면 ncnt(data.n과 nn까지의 최단거리)에 data.cnt(data.n유저와 인자로 받은 num유저 간의 최단거리) + 1 한 값을 대입한다. 이렇게 계산한 값을 chk배열에 대입하여 갱신하고, Q에 삽입하여 탐색한다. 

 

 

// get_kb( ) 함수

각 유저에 대한 케빈 베이컨 수를 구하는 함수이다. 

예컨대 1번 유저의 경우 1번부터 N번까지의 최단거리를 모두 더하면 그것이 바로 케빈 베이컨 수 이다. 

 

 

// get_least_kb( ) 함수

각 유저의 케빈 베이컨 수 중 가장 작은 것을 탐색한다. 

chk 배열을 memset 하는 이유는 각 유저별로 1번부터 N번유저 까지의 최단거리를 구해야하기 때문이다. 

BFS 함수를 이때 호출해주는 것도 동일한 이유이다.