백준 17089 세 친구(c++)

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

17089번: 세 친구

이 문제는 A, B, C의 각각의 친구의 수의 최솟값을 구하는 문제입니다. 우선적으로 A, B가 친구 관계인지 check해주고, A, B가 친구인 경우에 C가 친구인 경우를 구한다면, 시간 복잡도를 O(N^3)에서 O(N^2 + MN)으로 최소화할 수 있게 됩니다.

 

<코드>

#include <iostream>

using namespace std;

int a[4001][4001];
int degree[4001];

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>> n>> m;
    while(m--) 
    {
        int x,y;
        cin>>x>>y;
        a[x][y] = a[y][x] = 1;
        degree[x] += 1;
        degree[y] += 1;
        // degree : 친구의 수 1 증가
    }
    int ans = -1;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(a[i][j]) {
                for(int k=1;k<=n;k++) {
                   if(a[i][k] && a[j][k]) {
                        int sum = degree[i] + degree[j] + degree[k] - 6;
                        // A -> B,C B-> A,C C->A,B 인 경우 6가지 제외
                        if(ans == -1 || ans > sum) {
                            ans = sum;
                        }
                   } 
                }
            }
        }
    }
    // 친구 관계의 최대 수 M번 if(a[i][j])에 의해서 
    // 시간 복잡도 O(N^2 + MN)
    cout<<ans<<'\n';
}

a[x][y] = a[y][x] = 1은 서로 정점이 연결되어 있음을 의미하고, 친구관계임을 의미합니다. degree는 차수이자 간선의 수입니다. 쉽게 설명드리자면, 친구의 수라고 생각하시면 쉬울 것입니다.

if(a[i][j])문에 의해서, 복잡도를 최소화할 수 있는데 그 이유는 친구 관계의 수의 최댓값이 M이기 때문입니다. 그래서 시간 복잡도는 

O(N^2 + MN)으로 나타낼 수 있게 됩니다.