백준 17089번 - 세 친구 [JAVA]

TaeBong·2022년 12월 22일

알고리즘 풀이

목록 보기

10/14

🧩 문제

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을 출력한다.

예제

입력

출력

🎯 풀이

메모리	시간	코드길이
34312 KB	320 ms	1621 B

Point

세 친구 A, B, C를 골랐을 때 이 세 친구는 모두 각자가 친구여야만 가장 최소의 친구 수 합이 도출된다.

입력 처리

//친구 여부 저장(무향 그래프)
isFriend[a][b] = true;
isFriend[b][a] = true;

//친구 수 저장
++friendCnt[a];
++friendCnt[b];

친구 관계를 입력 받을 때, 친구 관계를 나타내는 이차원 배열에 무향그래프 형태로 저장해준다. 또한 각 번호의 사람마다 친구의 수를 증가해준다.

세 친구 찾기

for(int A = 1; A < N+1; A++) {
    for(int B = A+1; B < N+1; B++) {
        if(!isFriend[A][B]) continue;
        for(int C = B+1; C < N+1; C++) {
            if(!isFriend[C][A] || !isFriend[C][B]) continue;

            int sum = friendCnt[A] + friendCnt[B] + friendCnt[C] - 6;
            min = Math.min(min, sum);
        }
    }
}

세 친구를 고르기 위해 3중 for문을 돌린다. 이때, 두번째 친구는 첫번째 친구 이후 사람들을 고르고, 세번째 친구는 두번째 친구 사람들을 고르면 중복을 피할 수 있다. 또한 친구를 고를 때마다, 골라진 친구들이 친구 관계인지 아닌지 체크를 한다. 친구 관계가 아니라면 다른 친구를 고르러 간다. 세 친구를 모두 골랐다면 각 친구들의 친구 수를 모두 더 해준 뒤, 세 친구는 각자가 모두 친구 관계이므로 6을 빼준다.

⭐️ 전체 풀이 코드

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

public class BJ17089_세친구 {
    private static boolean[][] isFriend;
    private static int[] friendCnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        isFriend = new boolean[N+1][N+1];
        friendCnt = new int[N+1];

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            //친구 여부 저장(무향 그래프)
            isFriend[a][b] = true;
            isFriend[b][a] = true;

            //친구 수 저장
            ++friendCnt[a];
            ++friendCnt[b];
        }

        int min = Integer.MAX_VALUE;

        for(int A = 1; A < N+1; A++) {
            for(int B = A+1; B < N+1; B++) {
                if(!isFriend[A][B]) continue;
                for(int C = B+1; C < N+1; C++) {
                    if(!isFriend[C][A] || !isFriend[C][B]) continue;

                    int sum = friendCnt[A] + friendCnt[B] + friendCnt[C] - 6;
                    min = Math.min(min, sum);
                }
            }
        }

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