[백준] 친구 - 복습(플루이드-와샬)

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

 

플루이드-와샬 알고리즘

 - 모든 정점의 최단거리를 간단하게 구할수 있다. 시간복잡도는 O(a^3) 

 

2-친구의 수를 구한다고 했으므로 최단거리가 2이하인 값만 카운트 한다

 

#include <iostream>

using namespace std;

char Graph[51][51];
int graph[51][51];
int ret[51][51];
int INF = 987654321;

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

	for (int i = 0; i < N; i++)
		cin >> Graph[i];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			if (Graph[i][j] == 'N')
				graph[i][j] = INF;
			else
				graph[i][j] = 1;
		}

	for(int k = 0; k < N; k++)
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				if (graph[i][j] > graph[i][k] + graph[k][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
				}

	int cnt = 0;
	int maxFriend = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j)
				continue;
			if (graph[i][j] <= 2 && graph[i][j] != 0)
				cnt++;
		}
		if (cnt > maxFriend)
			maxFriend = cnt;
		cnt = 0;
	}

	cout << maxFriend << endl;
}