백준 17089, 세 친구

개요

문제 링크
골드 5, Graph
서로 연결된 세 점을 골라 세 점 사이 연결선이 아닌 다른 연결선의 개수의 합의 최솟갑 구하기

---

접근

1. 그래프 이론이라 하기에도 애매한 문제. 인접행렬을 이용하면 쉽게 풀린다. 두 사람의 연결 여부를 arr[a][b]와 같은 식으로 저장하고, 연결 개수를 미리 저장해 TLE를 방지한다.
2. 그리고 3명의 연결개수 합 - 6의 최솟값을 구해주면 된다.

---

Pseudo code

for (m)
    arr[a][b] = 1, arr[b][a] = 1
    count[a]++, count[b]++

for (i)
    for (j)
        if (!arr[i][j]) continue
        for (k)
            if (!arr[j][k]) continue
            if (!arr[k][i]) continue
            ans = min(count[a]+count[b]+count[c]-6)

---

Source code

#include <iostream>
using namespace std;

#define N 4010
bool f[N][N];
int d[N];

int main() {
    int n,m,a,b;
    cin>>n>>m;
    for (int i=0; i<m; i++) {
        cin>>a>>b;
        f[a][b] = 1, f[b][a] = 1;
        d[a]++, d[b]++;
    }
    int ans = 2e9;
    for (int a=1; a<=n; a++)
        for (int b=1; b<a; b++) {
            if (!f[a][b]) continue;
            for (int c=1; c<b; c++) {
                if (!f[b][c]) continue;
                if (!f[c][a]) continue;
                int v = d[a]+d[b]+d[c];
                ans = min(ans,v-6);
            }
        }
    cout << (ans==2e9?-1:ans);
}