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

우선 이 문제는 그래프 문제로 N 개의 정점이 주어지고 M개의 연결이 주어질때 '모든 정점'에서 '모든 정점'으로의 최단경로를 구하는 문제이다. 플로이드 와샬 알고리즘을 알고 있었다면 간단하게 해결할 수 있는 문제이다. 

 

하지만 플로이드 와샬 알고리즘을 몰랐기 때문에 인접리스트를 이용하여 DFS로 문제를 해결하였다. 각 정점에서 다른 정점까지 최단 경로를 구해야 하기 때문에 생각해낸 방법은 리스트에 찾고자 하는 정점이 있을경우 1번에 탐색 가능, 없을경우 리스트에 있는 정점으로 이동하여 다시 탐색하는 방법을 사용하였다. 어찌어찌 이상한 방법으로 문제를 해결하였지만 알고리즘 분류를 확인하고서 플로이드 와샬이라는 것을 알게 되었다.

 

우선 내가 푼 방법을 공유하고 다시 플로이드 와샬로 문제를 풀어보도록 하겠다.

• DFS

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

int n, m;
vector<int> adj[101];
bool visit[101];
int minCnt;

int solution(int start, int search, int cnt)
{
	visit[start] = true;

	bool isFind = false;
	for(int i = 0; i < adj[start].size(); i++)
	{
		if(adj[start][i] == search)
		{
			cnt++;
			isFind = true;
			break;
		}
	}

	if(isFind)
	{
		return cnt;
	}
	else
	{
		for(int i = 0; i < adj[start].size(); i++)
		{
			if(!visit[adj[start][i]])
			{
				minCnt = min(minCnt,solution(adj[start][i], search, ++cnt));
				visit[adj[start][i]] = false;
				cnt--;
			}
		}
		return minCnt;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for(int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
		adj[b].push_back(a);
	}


	pair<int, int> answer = { 987654321,0 };
	for(int i = 1; i <= n; i++)
	{

		int sum = 0;
		for(int j = 1; j <= n; j++)
		{
			memset(visit, false, sizeof(visit));
			minCnt = 987654321;
			int cnt = 0;
			if(i != j)
			{
				sum += solution(i,j, cnt);
			}
		}
		if(sum < answer.first)
		{
			answer = { sum,i };
		}
	}
	cout << answer.second;
}

• 플로이드 와샬

#include <iostream>
#include <vector>
#include <algorithm> 
#define INF 1e9 
#define MAX 101 
using namespace std; 

int n, m;
int graph[MAX][MAX]; // a에서 b로 가는 경로가 있으면 1, 없으면 0 

void floyd(){
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(i == j) continue; 
					
				// i에서 k로, k에서 j로 가는 경로가 있는데 
				else if(graph[i][k] != 0 && graph[k][j] != 0){
					// i에서 j로 직접 가는 경로가 없으면 
					if(graph[i][j] == 0){
						// k를 거쳐간다. 
						graph[i][j] = graph[i][k] + graph[k][j];
					}else{ 
						// 직접 가는 경로가 있으면 
						// 거쳐 가는 경로와 길이를 비교하여 최솟값으로 저장 
						graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]); 
					}
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		graph[x][y] = graph[y][x] = 1; 
	}

	floyd(); 

	int result = INF; // 최소 베이컨 수 
	int person; // 최소 케빈 베이컨 수를 갖는 사람 번호  

	for(int i = 1; i <= n; i++){
		// i에서 j로 가는 최소 경로 길이를 더한다.
		int sum = 0;
		for(int j = 1; j <= n; j++){
			sum += graph[i][j];
		}

		// 최소 베이컨 수와 그 수를 갖는 사람 번호 갱신 
		if(result > sum){ 
			result = sum; 
			person = i; 
		}
	}

	cout << person;
	
	return 0;
}