[ 백준 BOJ ] 1058번 - 친구 (C++)

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

 

생각 흐름

• 2-친구에 대한 조건을 보면 A-C, C-B일 때 A-B가 2-친구가 된다. 즉, A와 B가 특정 인물을 사이에 두고 이어질 수 있는지만 검증하면 된다.
• 사용한 알고리즘은 플로이드 워셜로 친구일 시에는 1의 가중치를 갖게 해서 특정 인물을 두고 이어져일 시에는 2의 가중치를 가지게 된다.
• 따라서 2 이하의 값을 카운팅해주면 쉽게 답을 구할 수 있다.

#include <iostream>
#include <string>

using namespace std;

int N;
int store[51][51];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    for(int i = 0; i<N; i++){
        string s;
        cin>>s;
        
        for(int j=0; j<s.size(); j++){
            if(s[j]=='Y') store[i][j] = 1;
            else store[i][j]=987654321;
        }
    }
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            for(int h = 0; h<N; h++){
                if(j==h) continue;
                store[j][h] = min(store[j][h], store[j][i]+store[i][h]);
            }
        }
    }
    
    int maxCount = 0;
    for(int i = 0; i<N; i++){
        int nowCount = 0;
        for(int j =0; j<N; j++){
            if(store[i][j]<=2){
                nowCount++;
            }
        }
        maxCount = max(maxCount, nowCount);
    }
    
    cout<<maxCount<<endl;
    
    return 0;
}