[BOJ 백준] 17089번 세 친구

문제

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

17089번: 세 친구

접근

친구 관계를 입력받아 두 사람(a, b)이 친구라면 2차원 배열의 값을 1로 주어 친구 관계임을 나타낸다. 동시에 특정 인물 a가 몇 명의 친구를 가졌는지를 저장해주는 배열의 값도 증가시켜준다. 다음으로 임의의 사람 i와 j가 친구라면 임의의 사람 k와 i, k와 j가 친구인지 확인해준다. 세 사람이 친구인지 확인했다면 i, j, k가 가진 친구의 수를 더한 뒤 중복되는 서로의 존재의 수(6)을 빼준다. 

코드

#include <iostream>

using namespace std;

int f[4010][4010];
int have_f[4010];

int main() {
    int n, m, a, b, counter, answer = -1;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b; 
        f[a][b] = 1;
        f[b][a] = 1;
        have_f[a]++;
        have_f[b]++;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (f[i][j] == 1) {
                for (int k = 1; k <= n; k++) {
                    if (f[j][k] == 1 && f[i][k] == 1) {
                        counter = have_f[i] + have_f[j] + have_f[k] - 6;
                        if (answer == -1 || counter < answer)
                            answer = counter;
                    }
                }
            }
        }
    }

    cout << answer;

    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study