17089. 세 친구

 

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

17089번: 세 친구

 

 

 

 

 

처음 문제를 읽고 문제가 이해가 안갔다. 문제를 쉽게 정리하자면,

 

1. 세 사람을 골라야 된다.

2. 세 사람은 서로 친구 관계여여함 ( 친구 관계는 입력을 통해 주어짐 )

3. 세 사람이 친구관계이면서 각각의 사람이 가진 친구 수의 합의 최소값을 구해야 함.

 

예를들어, A, B, C가 서로 친구관계일때, A의 친구수 + B의 친구수 + C의 친구수의 최솟값을 구하라는 뜻

만약 세 사람이 서로 친구관계인 경우가 없으면 -1을 출력..

 

최대 사람의 수는 4000명인데 4000명 중에 3명을 고르는 경우는 4000 C 3 ~= 4000^3 = 64,000,000,000...

모든 사람을 조사하는 방법은 3중 for문을 사용해서 조사를 하니 당연히 시간초과가 나겠지?????

 

따라서 방법을 조금 우회해야 한다. 

고른 두명의 사람이 친구 관계일 때만, 나머지 한명을 조사해 세 사람이 서로 친구관계인지 확인하면 2번 조건을 충족하면서 2번 조건을 만족 시킬 수 있다. 이렇게 하면 최대 O(N^2 + NM) 으로 줄일 수 있다.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;
int n,m;
int a[4001][4001];
vector<int> d(4001);
int f1,f2;
int ans = -1;

int main()
{
    FASTio;
    cin >> n >> m;

    for(int i=0;i<m;i++)
    {
        cin >> f1 >> f2;   
        a[f1][f2] = 1;

        // 친구관계 오름차순 입력이라는 조건이 없으므로 내림차순입력인 경우
        a[f2][f1] = 1;

        d[f1] +=1; // f1의 친구수 1증가
        d[f2] +=1; // f2의 친구수 1증가

    }

    // A,B가 친구일 경우에만 C를 구한다 -> O(n*n + mn)
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            // i와 j가 친구라면
            if(a[i][j]==1)
            {
                for(int k=j+1;k<=n;k++)
                { 
                    // i와 k가 친구이고 j와 k도 친구인 즉 세친구가 모두 서로 친구인경우    
                    if(a[i][k]==1 && a[j][k]==1)    
                    {   
                        int sum = d[i] + d[k] + d[j] - 6;
                        if(ans==-1 || ans>sum)
                            ans = sum;
                    } 
                }
            }
        }
    }   



    // // O(n*n*n) -> 시간초과
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=i+1;j<=n;j++)
    //     {
    //         for(int k=j+1;k<=n;k++)
    //         { 
    //             if(a[i][k]==1 && a[j][k]==1 && a[i][j]==1)    
    //             {   
    //                 int sum = d[i] + d[k] + d[j] - 6;
    //                 if(ans==-1 || ans>sum)
    //                     ans = sum;
    //             } 
    //         }
    //     }
    // }   


    cout << ans;


    return 0;
}