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

문제

풀이

인접행렬로 그래프를 구현하고 리스트에 노드마다 친구의 수를 넣는다.
3중 for문을 돌리면서 세 명이 친구이면 총 친구를 세고 min값을 갱신한다.

코드

friend = new int[N+1][N+1];
        nums = new int[N + 1];
        for (int i = 0; i < M; i++) {
            int A = fr.nextInt();
            int B = fr.nextInt();
            friend[A][B] = 1;
            friend[B][A] = 1;
            nums[A]++;
            nums[B]++;
        }

friend[][] - 인접행렬
nums[] - 친구 수 저장 배열

for (int i = 1; i < N; i++) {
            for (int j = 1; j <= N; j++) {
                if(friend[i][j] != 1 || friend[j][i] != 1) continue;
                if(i==j)continue;
                for (int k = 1; k <= N; k++) {
                    if(friend[i][k] != 1 || friend[j][k] != 1 || friend[k][j] != 1 || friend[k][i] != 1) continue;
                    if(i == k || j == k) continue;
                    int cnt = 0;
                    cnt += nums[i] - 2;
                    cnt += nums[j] - 2;
                    cnt += nums[k] - 2;
                    ans = Math.min(cnt, ans);
                }
            }
        }

자기자신이거나 친구가 아닌 node를 탐색하면 continue
모든 조건을 만족하면 cnt에 총 친구 수를 더하고 min 값을 갱신

전체코드

package baekjoon._17089;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[][] friend;
    static int[] nums;

    public static void input() {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        M = fr.nextInt();
        friend = new int[N+1][N+1];
        nums = new int[N + 1];
        for (int i = 0; i < M; i++) {
            int A = fr.nextInt();
            int B = fr.nextInt();
            friend[A][B] = 1;
            friend[B][A] = 1;
            nums[A]++;
            nums[B]++;
        }
    }

    public static void pro() {
        int ans = Integer.MAX_VALUE;

        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= N; j++) {
                if(friend[i][j] != 1 || friend[j][i] != 1) continue;
                if(i==j)continue;
                for (int k = 1; k <= N; k++) {
                    if(friend[i][k] != 1 || friend[j][k] != 1 || friend[k][j] != 1 || friend[k][i] != 1) continue;
                    if(i == k || j == k) continue;
                    int cnt = 0;
                    cnt += nums[i] - 2;
                    cnt += nums[j] - 2;
                    cnt += nums[k] - 2;
                    ans = Math.min(cnt, ans);
                }
            }
        }

        if(ans == Integer.MAX_VALUE) ans = -1;
        System.out.println(ans);
    }

    public static void main(String[] args) {
        input();
        pro();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

처음 봤을 때는 인접리스트로 해결해야하는 줄 알았는데 행렬이 훨씬 빠르고 쉽게 풀렸다.