[C++] 백준 1058번: 친구

문제 링크

1058번: 친구

문제 요약

두 사람이 직접 친구 관계이거나, 한 사람을 건너 친구인 경우를 2-친구라고 한다. 2-친구가 가장 많은 사람의 2-친구 수를 구해야 한다.

접근 방법

N은 최대 50정도밖에 되지 않습니다. 또 가중치가 없는 그래프입니다.
여러 접근을 생각해 볼 수 있습니다.

1. N번 BFS
2. N번 DFS(깊이 2까지)
3. 플로이드-와샬 알고리즘

제 경우에는 플로이드-와샬 알고리즘을 사용했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int dp[51][51];

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = INT_MAX;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			char c;
			cin >> c;

			if (i == j)
				continue;

			if (c == 'Y')
				dp[i][j] = 1;
		}
	}

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (dp[i][k] != INT_MAX && dp[k][j] != INT_MAX)
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				continue;
			if (dp[i][j] <= 2 && dp[i][j])
				cnt++;
		}
		ans = max(ans, cnt);
	}
	
	cout << ans;
	return 0;
}