1058번

1058번 - 친구

처음에 문제를 읽고 무슨말인가 했지만

그냥 어떤 한 정점에서 거리가 2이하인 값들의 총 갯수들 중에서 최대값을 구하는 문제였다.

그래서 모든 정점을 비교할 필요가 있었기 때문에 플로이드 알고리즘을 이용했다.

그리고 마지막에 자기 자신으로 가는 값을 하나 빼줬다.

<정답 코드>

#include<iostream>
 
using namespace std;
 
int D[51][51];
const int INF = 987654321;
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        char temp[51];
        scanf("%s", &temp);
        for (int j = 0; j < n; j++)
        {
            if (temp[j] == 'Y')
            {
                D[i][j] = 1;
            }
            else
            {
                if (i == j)
                {
                    D[i][j] = 0;
                }
                else
                {
                    D[i][j] = INF;
                }
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (D[i][j] > D[i][k] + D[k][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int temp = 0;
        for (int j = 0; j < n; j++)
        {
            if (D[i][j] <= 2)
            {
                temp++;
            }
        }
 
        ans = temp > ans ? temp : ans;
    }
 
    printf("%d\n", ans-1);
    return 0;
}