[C++] 백준 1058 친구

https://www.acmicpc.net/problem/1058
제목 : 친구
solved.ac 난이도 : Silver II

풀이

A의 2-친구는 A, B가 친구이고, A와 친구이며 B와 친구인 C가 존재해야 한다.
예를 들어 a, b, c, d 4명의 사람이 있다고 가정하면.
a 와 b가 서로 친구이면 "2-친구"이고,
a와 c가 친구이며 c와 d가 친구이면 a와 d는 "2-친구"이다.
즉, 한 사람과 거리가 1인 사람과 거리가 2인 사람의 수를 구하면 되는 것이다.
플로이드 와샬 알고리즘을 활용하여 풀었다.

#include <iostream>
#include <vector>

using namespace std;

int getfamus(vector<string>& friends, int& N) {
    vector<vector<int>> famus(N, vector<int>(N, 99999999));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (friends[i][j] == 'Y') famus[i][j] = 1;
            if (i == j) famus[i][j] = 0;
        }
    }

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

    int maxfamus = 0;
    for (auto i : famus) {
        int count = 0;
        for (int j : i) {
            if (j != 0 && j <= 2) {
                count++;
            }
        }
        maxfamus = max(count, maxfamus);
    }
    return maxfamus;
}

int main()
{
    int N;
    string people;
    vector<string> friends;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> people;
        friends.push_back(people);
    }
    cout << getfamus(friends, N);
}