[백준/BOJ] 1058 친구

문제 : 1058 친구

1058번: 친구

친구, 친구의 친구가 가장 많은 사람의 친구 수를 출력하는 문제이다.

거리가 2 이내인 정점의 개수의 최댓값을 구하면 되므로

각 정점마다 BFS로 체크하다 거리가 2 이상 넘어가면 탈출하도록 코드를 짜고

최댓값을 취합해 출력하면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, ans=0;
string arr[55];
ll BFS(ll st){
    ll visit[55], ret=0;
    fill(&visit[0],&visit[54],-1);
    queue<ll> q;
    q.push(st);
    visit[st]=0;
    while (!q.empty()){
        ll x=q.front();
        q.pop();
        if (visit[x]>=2)
            break;
        for (int i=0;i<N;i++){
            if (arr[x][i]=='Y' && visit[i]==-1){
                visit[i]=visit[x]+1;
                q.push(i);
                ret++;
            }
        }
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i=0;i<N;i++){
        cin >> arr[i];
    }
    for (int i=0;i<N;i++){
        ans=max(ans,BFS(i));
    }
    cout << ans;
    return 0;
}