[BOJ] 17089 - 세 친구

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

BOJ - 세 친구

문제 유형: 브루트 포스, 그래프, 정렬

문제 난이도: Gold V

시간 제한: 2초

메모리 제한: 512MB

 

문제

N명의 사람이 있고, 여기서 세 사람 A, B, C를 고르려고 한다. 세 사람은 모두 친구여야 한다.

세 사람을 고르는 방법은 매우 많이 있을 수 있다. 이때, A의 친구 수 + B의 친구 수 + C의 친구 수가 최소가 되어야 한다. 친구 수의 합을 계산할 때, 세 사람은 빼고 계산해야 한다. 즉, A의 친구 수를 계산할 때, B와 C는 빼고 계산해야 하고, B의 친구 수를 계산할 때는 A와 C, C의 친구 수를 계산할 때는 A와 B를 빼고 계산해야 한다.

 

입력

첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친구라는 것을 의미한다.

사람은 1번부터 N번까지 번호가 매겨져 있다. 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

 

출력

첫째 줄에 A의 친구 수 + B의 친구 수 + C의 친구 수의 최솟값을 출력한다. 만약, 문제 조건대로 세 사람을 고를 수 없는 경우에는 -1을 출력한다.

 

풀이

브루트 포스로 3중for문을 돌리면 풀린다.

m <= 4000인 희소한 행렬이기에 가능하다.

대신, 빠르게 하기 위해, 정렬하고 반복적인 계산을 피한 O(n^3)이다.

 

세 노드의 총 차수의 합 - 6이 후보 값들이다. 이들 중 최소값을 출력한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end());
    }

    int ans = INT_MAX;
    for (int a = 1; a <= n; a++) {
        int bIdx =
            lower_bound(adj[a].begin(), adj[a].end(), a + 1) - adj[a].begin();
        for (int j = bIdx; j < adj[a].size(); j++) {
            int b = adj[a][j];
            int cIdx = lower_bound(adj[b].begin(), adj[b].end(), b + 1) -
                       adj[b].begin();
            for (int k = cIdx; k < adj[b].size(); k++) {
                int c = adj[b][k];
                if (binary_search(adj[c].begin(), adj[c].end(), a)) {
                    int s = adj[a].size() + adj[b].size() + adj[c].size() - 6;
                    ans = min(ans, s);
                }
            }
        }
    }

    if (ans == INT_MAX) {
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}