[그래프] 백준 1389 c++ 케빈 베이컨의 6단계 법칙

오 어려움

예전에 풀려고 했다가 못 풀었던 거 같음

 

브루트포스가 아닐까 하는 생각

    ...
    for(int i=1; i<N+1; i++)
    {
        for(int j=1; j<N+1; j++)
        {
            if(j != i)
            {
                if(min_dist[i][j] == 0)
                {
                    // j가 i의 친구라면
                    if(find(con[i].begin(), con[i].end(), j) != con[i].end())
                    {

                    }
                }
            }
        }
    }

-> 이 난리 치다보니까 아닌 거 같음

 

브루트포스 틀림 

 

어려워

 

bfs 탐색하면서 도달 시 depth를 더해주면 되지 않을까

근데 depth 를 어떻게 구하지

(depth가 아니라 level이라고 해야지)

 

memset의 헤더를 include하지 않아 컴파일 에러 한번 떠주고 

 

하 토나올 거 같음

---

• 정답 제출 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

int N, M;
int arr[101][101] = {0,};
int visited[101] = {0, };
vector <int> next_bfs;
vector <int> res_v;

int res = 0;

void bfs(int r){

    if(!visited[r])
        visited[r] = 1;

    int level = 1;

    while(!next_bfs.empty())
    {
        int size = next_bfs.size();
        for(int j=1; j<=size; j++)
        {
            r = *next_bfs.begin();
            next_bfs.erase(next_bfs.begin());

            for(int i=1; i<N+1; i++)
            {
                if(arr[r][i] && !visited[i])
                {
                    res += level;
                    visited[i] = 1;
                    next_bfs.push_back(i);
                }
            }
        }
        level++;

    }
}

int main(){
    cin >> N >> M;

    int min_dist[101][101] = {0, };

    vector<vector<int> > con;
    vector <int> v;
 
    con.push_back(v);
    
    // 친구 배열 채워주기
    for(int i=0; i<M; i++)
    {
        int r, c;
        cin >> r >> c;
        arr[r][c] = 1;
        arr[c][r] = 1;
    }
    
    for(int i=1; i<N+1; i++)
    {
        res = 0;
        memset(visited, 0, sizeof(visited));
        next_bfs.push_back(i);
        bfs(i);
        
        res_v.push_back(res);
    }

    cout << min_element(res_v.begin(), res_v.end()) - res_v.begin() + 1 << endl;
    return 0;
}