세 친구

문제

문제 설명

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번까지 번호가 매겨져 있다. 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

입출력 예

입력	출력
5 6
1 2
1 3
2 3
2 4
3 4
4 5	2
7 4
2 1
3 6
5 1
1 7	-1

입출력 예 설명

아이디어

세 명이니까 굳이 조합 구할 필요 없이 반복문으로 탐색 후 -6 하면 됨

제출 코드

import java.io.*;
import java.util.*;

/*
 @author ranuinclulus
 @since 2024.10.28
 @link https://www.acmicpc.net/problem/17089
 @timecomplex
 @performance
 @category
 @note
 */
public class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder builder = new StringBuilder();
    static StringTokenizer tokenizer;
    static int n, m;
    static boolean[][] friends;
    static int[] friendsNum;
    static int minValue = Integer.MAX_VALUE;

    public void solution() throws IOException {
        tokenizer = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(tokenizer.nextToken());
        m = Integer.parseInt(tokenizer.nextToken());

        friends = new boolean[n][n];
        friendsNum = new int[n];

        for (int i = 0; i < m; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int a = Integer.parseInt(tokenizer.nextToken()) - 1;
            int b = Integer.parseInt(tokenizer.nextToken()) - 1;
            friends[a][b] = true;
            friends[b][a] = true;
            friendsNum[a]++;
            friendsNum[b]++;
        }

        for (int first = 0; first < n; first++) {
            for (int second = first + 1; second < n; second++) {
                if (!friends[first][second]) continue;
                for (int third = second + 1; third < n; third++) {
                    if (!friends[first][third] || !friends[second][third]) continue;
                    int count = friendsNum[first] + friendsNum[second] + friendsNum[third] - 6;
                    minValue = Math.min(minValue, count);
                }
            }
        }
        if (minValue == Integer.MAX_VALUE) minValue = -1;
        builder.append(minValue);
        writer.write(builder.toString());
        writer.flush();

    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}