(C++) 백준 17089 세 친구

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

그래프 표현 방식 두가지를 사용해서 문제 풀이했다.

• vector를 사용해서 그래프 표현 : dfs를 사용해 탐색하기 위함
• array를 사용한 그래프 표현 : 시작 친구~마지막 친구가 서로 친구인지 확인하기 위함

간단하게 풀고싶어서 함수 인자로 현재 위치, 시작한 위치, 선택된 친구 갯수, 선택된 친구들의 친구 수 합 을 넘겼는데 너무 복잡해보이는건 아닌지ㅎ

다른 사람들 풀이 보면 3중 for문으로 많이 풀었다. 범위가 적어서 이렇게 풀어도 괜찮은거같다.
하지만 나는 정형된 풀이로만 풀수있는 밥오라고~

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v(4005);
bool isfriend[4005][4005];
bool isvisited[4005];
int theNumoffriend[4005];

int ans=-1;

void dfs(int x, int start, int cnt, int num){

    if(cnt==3){
        if(!isfriend[start][x]) return;

        int cnt=0;
        if(ans!=-1) ans = min(num-6, ans);
        else ans = num-6;
        return ;
    }


    for(int i=0; i<theNumoffriend[x]; i++){
        int nxt = v[x][i];

        if(isvisited[nxt]) continue;
        isvisited[nxt]=true;
        dfs(nxt, start, cnt+1, num+theNumoffriend[nxt]);
        isvisited[nxt]=false;
    }


}



int main() {

    int N, M;

    cin>>N>>M;

    int a,b;
    for(int i=0; i<M; i++){
        cin>>a>>b;

        v[a].push_back(b);
        v[b].push_back(a);

        isfriend[a][b]=true;
        isfriend[b][a]=true;

        theNumoffriend[a]++;
        theNumoffriend[b]++;
    }


    for(int i=1; i<=N; i++){
        if(isvisited[i]) continue;
        isvisited[i]=true;
        dfs(i, i, 1, theNumoffriend[i]);
    }


    cout<<ans;
}