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

문제 출처: https://www.acmicpc.net/problem/1389

풀이

문제 조건에맞게 예제를 그려서 보면 문제에서 원하는 답은 어떤정점에서 각 정점으로 가는 최단거리의 합이 가장 작은 정점임을 알 수 있습니다.

문제를 읽어보면 플로이드와샬 알고리즘으로 풀 수 있음을 짐작 할 수 있습니다.

플로이드 와샬 알고리즘으로 풀 때 한 노드에서 다른 노드로 가는 길이 없을 때를 0이아닌 INF로 채워넣고 푸는 방법과 0으로 초기화시켜놓고 푸는

방법이 있는데, 0으로 초기화 시켜서 풀 경우, "길이 없음"과 최단거리의 의미가 충돌되므로 출발->도착 하는 지점이 없을 경우는

일단 map[i][j]를 출발->거치고->도착하는 값으로 설정시켜줘야합니다. 

저는 INF로 채워놓고 풀었습니다.(취향 차이인 것 같습니다.)

main문에서 배열을 INF로 채워넣지않고(0으로해놓고) 플로이드 3중for문내부 의 주석을 해제하면 0으로 놓고 푸는 풀이가 됩니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int INF =10000000;
int n, m, map[101][101], a, b;
int index = 0;
void floyed();
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			map[i][j] = INF;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;
	}
	floyed();
	cout << index << '\n';
}
void floyed()
{
	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;
				/*if (map[i][k] && map[k][j])
				{
					if (map[i][j] == 0)
						map[i][j] = map[i][k] + map[k][j];
					else map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
				}*/
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
			}
		}
	}
	int val = 10000000;
	for (int i = 1; i <= n; i++)
	{
		int temp = 0;
		for (int j = 1; j <= n; j++)
		{
			if (i == j)continue;
			temp += map[i][j];
		}
		if (val > temp)
		{
			val = temp;
			index = i;
		}
	}
}

결과