백준 1058번 친구 - C++ 풀이

---

 

1. 어떤 사람 p의 2-친구수는 p가 아닌 나머지 모든 사람에 대해 2-친구 여부를 판별해서 구할 수 있다.
2. 모든 사람의 2-친구수를 각각 구한 뒤 그 중 최대값을 찾는다.

 

1. 어떤 사람 p의 2-친구수는 p가 아닌 나머지 모든 사람에 대해 2-친구 여부를 판별해서 구할 수 있다.

 어떤 사람 p의 2-친구수는 k(k != p)인 모든 사람에 대해 친구 여부를 판별해서 구할 수 있다. 두 사람 A, B가 2-친구 사이인지 구하려면 두 사람 모두와 친구인 사람 C가 있는지 찾아야 하므로 O(N)의 시간복잡도가 든다. 따라서 어떤 사람 p의 2-친구수를 구하는데는 O(N^2)의 시간복잡도가 들게 된다.

 

2. 모든 사람의 2-친구수를 각각 구한 뒤 그 중 최대값을 찾는다.

 모든 사람에 대해 2-친구수를 구한 뒤, 그 중 최대값을 출력한다. O(N^2)의 1번 과정을 모든 사람에 대해 반복하므로 전체 시간복잡도는 O(N^3). N이 매우 작으므로 브루트포스로 해결할 수 있다.

 

반응형

---

#include <iostream>

using namespace std;

int N;
bool friends[51][51];

bool isFriend(int a, int b) {
    if (a == b) return false;
    if (friends[a][b]) return true;
    for (int c=0; c<N; c++) {
        if (friends[a][c] && friends[b][c]) return true;
    }
    
    return false;
}

int count2Friends(int p) {
    int ret = 0;
    
    for (int i=0; i<N; i++) {
        if (isFriend(p, i)) ret++;
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    string S;
    for (int i=0; i<N; i++) {
        cin >> S;
        for (int j=0; j<N; j++) {
            friends[i][j] = S[j] == 'Y';
        }
    }
    
    int max2Friends = 0;
    for (int i=0; i<N; i++) {
        max2Friends = max(max2Friends, count2Friends(i));
    }
    
    cout << max2Friends;

    return 0;
}