백준 1389 c++ "케빈 베이컨의 6단계 법칙" -PlusUltraCode-

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

 

 

[필자 사고]

문제를 읽고 이해를 해보면 다음과 같다.

1. 얼만큼의 친구들이 건너건너 있냐 => 모든 경로의 최단경로를 구한뒤 합을 구하면 케빈 베이컨법칙의 합이 만들어진다.

2. 모든 경로를 구하기 위해 플로이드 와샬 알고리즘이 재격이다.

 

이 문제에서 조심해야 될 점은 가중치 값을 1로 설정하고 se만 설장할게 아니라 es도 양방향 선택해서 주입해야된다.

 

아래는 소스코드 해설이다.

 

 

Input() 함수

• Input() 함수는 먼저 사용자로부터 노드의 수 N과 간선의 수 M을 입력받는다.
• 그런 다음, 2차원 벡터 arr를 노드의 개수에 맞춰 초기화한다. 각 노드 간의 초기값은 매우 큰 수인 99999로 설정되며, 자기 자신으로의 경로(arr[i][i])는 0으로 설정된다.
• 이후, 사용자로부터 입력받은 간선 정보(s, e)를 통해 두 노드가 연결되어 있음을 2차원 배열에 반영하고, 양방향으로 연결되었음을 고려해 arr[s][e]와 arr[e][s] 모두 1로 설정한다.
•  
• Floid_Warshall() 함수 Floid_Warshall() 함수는 플로이드-와샬 알고리즘을 사용하여 모든 노드 간의 최단 경로를 계산한다.
• 세 개의 중첩된 반복문을 사용해 중간 노드 k를 경유하는 경로가 더 짧은지 확인하고, 더 짧으면 그 값을 갱신한다. 이렇게 하면 모든 노드 쌍에 대한 최단 경로가 구해진다.

 

• GameStart() 함수 GameStart() 함수는 먼저 Floid_Warshall()을 호출하여 모든 노드 간의 최단 경로를 구한 후, 각 노드에서 다른 모든 노드까지의 최단 경로의 합을 계산한다.
• 이를 위해 resultList라는 벡터를 사용하여 각 노드별 경로 합계를 저장한다.
• 그 후, min_element 함수를 사용하여 최소 합계를 찾고, 그 합계를 가진 노드를 출력한다. 이는 다른 노드들과의 총 거리 합이 가장 작은 노드, 즉 중심 노드를 구하는 과정이다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

int N, M;
vector<vector<int>> arr;

void Input() {
	cin >> N >> M;
	arr.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		arr[i].resize(N + 1, 99999);
		arr[i][i] = 0;
	}

	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		arr[s][e] = 1;
		arr[e][s] = 1;
	}
}

void Floid_Warshall() {

	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				if (arr[s][e] > arr[s][k] + arr[k][e]) {
					arr[s][e] = arr[s][k] + arr[k][e];
				}
			}
		}
	}
}

void GameStart() {
	Floid_Warshall();

	vector<int> resultList;
	resultList.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		int sum = 0;
		for (int k = 1; k <= N; k++) {
			if (arr[i][k] == 99999)continue;
			sum += arr[i][k];
		}
		resultList[i] = sum;
	}

	int minNum = *min_element(resultList.begin()+1, resultList.end());
	
	for (int i = 1; i <= N; i++) {
		if (minNum == resultList[i]) {
			cout << i;
			return;
		}
	}
}

int main(void) {
	Input();
	GameStart();
}