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

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

1058번: 친구

 

2-친구를 구하는 문제다. 2-친구라는건 A와 B가 친구거나, A와 B가 친구가 아니더라도, 인싸인 C에 의해 연결될 수 있는 사이를 말하는 것이다. A-B 이거나 A-C-B 인 관계를 의미한다.

 

시간이 매우 오래 걸리는 방법을 택한듯 하다. 거의 브루트포스 아닐까 싶다. 내 풀이가 그렇게 좋은 풀이는 아닌것 같다.

#include <iostream>
#include <string.h>
#include <algorithm>
#define MAX_N 50
using namespace std;

int main(){
    int N;
    string friends_each[MAX_N];
    int two_friend_cnt[MAX_N] = {0};
    cin >> N;
    for(int n=0; n<N; n++)
    {
        cin >> friends_each[n];
    }
    for(int n=0; n<N; n++)
    {
        for(int i=0; i<N; i++)
        {
            if(n==i)
            {
                continue;
            }
            if(friends_each[n][i]=='Y')
            {
                two_friend_cnt[n]++;
            }
             else if(friends_each[n][i]=='N')
            {
                for(int j=0; j<N; j++)
                {
                    if((friends_each[n][j] =='Y') && (friends_each[i][j] == 'Y'))
                    {
                        two_friend_cnt[n]++;
                        break;
                    }
                }
            }
        }
    }
    int ans = *max_element(two_friend_cnt,two_friend_cnt+N);
    cout << ans << "\n";
}