백준 1389(케빈 베이컨의 6단계 법칙 ) 플로이드 와샬

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

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

가장 적은 거리로 연결되는 index를 찾는 전형적인 그래프 문제.

 

dfs로 풀었지만 dfs를 이용해서 풀었을 때 정확한 시간복잡도 계산도 모르겠고, 해서 다른 알고리즘을 찾아보았다.

 

플로이드 와샬 

 

모든 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘

 

 

a->b로 가는 최단 경로를 알아보려면, (a -> b) vs (a->c  + c->b) 이런식으로 모든 정점이 중심이 되는 경우를 계산하고, 더 적게 걸리는 값으로 최신화를 해주면 결과적으로 인접매트릭스가 모두 최단 거리로 구성이 된다.

 

if (people[시작점][종점] > people[시작점][지나는 중심] + people[지나는 중심][종점])
people[시작점][종점] = people[시작점][지나는 중심] + people[지나는 중심][종점];

 

이렇게 코드가 짜여진다. 

 

이 문제에서는 간선의 방향이 양방향이므로 입력을 할 때, people[a][b] 와 people[b][a]를 동시에 해주었다. 

 

#include<iostream>
using namespace std;
#define MAX 101

int N, M, a, b, index, sum, res=987654321;
int people[MAX][MAX];

int main() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) people[i][j] = 0; // 자기 자신과의 거리
			else {
				people[i][j] = res; //처음에 직접 연결이 되지 않은 부분은 INF로 초기화해준다. 
			}
		}
	}
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		people[a][b] = 1;
		people[b][a] = 1;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int z = 1; z <= N; z++) {
				if (people[j][z] > people[j][i] + people[i][z])
					people[j][z] = people[j][i] + people[i][z];
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		sum = 0;
		for (int j = 1; j <= N; j++) {
			sum += people[i][j]; 
		}
		if (sum < res) {
			res = sum;
			index = i;
		}
	}
	cout << index << "\n";
}

예제 입력

5 5

1 3 1 4 4 5 4 3 3 2

 

최종 matrix

 

0 2 1 1 2
2 0 1 2 3
1 1 0 1 2
1 2 1 0 1
2 3 2 1 0

 

이런 단순 연결 여부를 물어보고, 하는 문제보다는 각각의 거리가 존재할 때 더욱 필요한 알고리즘인 것 같다.