BaekJoon 1389번: 케빈 베이컨의 6단계 법칙(C++)

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

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

풀이법

1) DFS를 활용하여 최소를 구하는 문제이다.

2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다.

3) sort를 활용하여 비교를 진행하여 케빈 베이컨의 수가 가장 작은 사람을 출력 시에 가장 작은 값이 여러 명일 경우에는 번호가 가장 작은 사람을 출력하였다.

4) tmpt 배열을 통해 시작 node에서와의 거리를 구해 주었고 이를 최종적으로 합하였다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;

int n, m;
int arr[101][101];
bool visited[101];
int tmpt[101][101];
bool cmp(pair<int, int>a, pair<int, int>b)
{
	if (a.first == b.first)
		return a.second < b.second;
	else
		return a.first < b.first;
}
bool checkVisit()
{
	for (int i = 1; i <= n; i++)
	{
		if (visited[i]==false)
			return false;
	}
	return true;
}
int bfs(int a)
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			tmpt[i][j] = 0;

	queue<pair<int, int>>q;
	q.push({ a,0 });
	tmpt[a][a] = 0;
	visited[a] = true;
	while (!q.empty())
	{
		int now = q.front().first;
		int cnt = q.front().second;
		q.pop();
		for (int i = 1; i <= n; i++)
		{
			if (arr[now][i] == 1 && !visited[i])
			{
				q.push({ i,cnt + 1 });
				tmpt[a][i] = cnt + 1;
				visited[i] = true;
			}
		}
	}
	int tempSum=0;
	for (int i = 1; i <= n; i++)
	{
		tempSum+= tmpt[a][i];
	}
	return tempSum;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	vector<pair<int,int>> ans;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		memset(visited, false, sizeof(visited));
		int tmp=bfs(i);
		ans.push_back({ tmp,i });
	}
	sort(ans.begin(),ans.end(),cmp);
	
	cout << ans[0].second;
}