[백준 17089] 세 친구, C++

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

17089번: 세 친구

 본 문제는 n명의 사람 중 a, b, c 세 명을 선택한다. a, b, c 세 명 다 친구 일 경우 각각 친구의 수의 합을 구한다. 단, a의 친구 수를 계산할 때, b와 c는 빼고 계산해야 하고, b의 친구 수를 계산할 때는 a와 c, c의 친구 수를 계산할 때는 a, b를 빼고 계산해야 한다.

예를 들어 n = 5일 때, 친구인 경우는 (1 2 3), (1 2 4), (1 2 5), (1 3 4), ... (2 4 5), (3 4 5) 가 있다. 5명의 사람 중 중복없이, 오름차순으로 정렬한 형태로 나온다.

1. a를 선택한다.
2. a보다 큰 b를 선택한다.
3. a와 b의 관계를 확인한다.
4. b보다 큰 c를 선택한다.
5. (a, c), (b, c)의 관계를 확인한다.
6. 친구의 수를 더하고 조건에 맞게 6을 뺀다.

#include <cstdio>
#include <vector>
 
using namespace std;
 
bool chk[4001][4001];
int frien[4001];
 
int main() {
    int n, m;
    int ans = -1;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        frien[x] += 1;
        frien[y] += 1;
        chk[x][y] = true;
        chk[y][x] = true;
    }
    for (int a = 1; a <= n; a++) {
        for (int b = a+1; b <= n; b++) {
            if (chk[a][b]) {
                for (int c = b+1; c <= n; c++) {
                    if (chk[a][c] && chk[b][c]) {
                        int sum = frien[a] + frien[b] + frien[c] - 6;
                        if (ans == -1 || ans > sum) ans = sum;
                    }
                }
            }
        }
    }
    printf("%d\n", ans);
}