[C++] 백준 1389 케빈 베이컨의 6단계 법칙

 

💟

오랜만에 DFS/BFS 공부를 열심히하고 풀어보았다.

풀고나니까 쉬운 난이도였다.

 

1. 먼저 n명의 사람  케빈 베이컨 수를 구해야 해서 go를 인원수 만큼 반복해서 돌린다.

2. 현재 나의 번호를 기준으로해서 n-1명이 각각 몇번만에 갈 수 있는지 체크해야함
    따라서, go함수 내에서 n만큼 돌린다.

3. bfs 함수로 들어와서 케빈의 수를 구한다.

4. 케빈의 수를 구해야하는 사람(goal)이라면 k 에 현재 p값이 min이라면 집어넣기.

5. 아니라면 방문했음을 체크하고 bfs를 한번더 돌린다. 
    bfs가 끝나면 방문 체크해제를 해야함.

6. 난 vector<pair> 로 result를 꾸렸다. 인덱스 오름차순으로 정렬 후 답을 출력한다.

      

      

      

    
    

      <bash />
    
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;
int INF = 987654321;
int n, m, ret=INF, visited[101];
int k=INF;
vector<int> lst[101];
vector<pair<int,int>> result;

bool comp(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second < b.second;
}

void bfs(int num, int goal, int p) {
    //cout <<"num:" << num << " goal:"<< goal << " p:"<< p << "\n";
    for(int j : lst[num]) {
        if(visited[j]) continue;
        if(j == goal) {
            k = min(k, p);
        } else {
            visited[j] = 1;
            bfs(j, goal, p+1);
            visited[j] = 0;
        }   
    }
}
void go(int num) {
    //cout << "----------" << num << "------------\n";
    visited[num] = 1;
    int sum=0;
    for(int i=1; i<=n; i++) {
        if(num == i) continue;
        k = INF;
        bfs(num, i, 1);
        //cout << k << " ";
        sum += k;
    }
    //cout << "\n";
    result.push_back({num, sum});
}

int main()
{
    cin >> n >> m;
    int a, b;
    for (int i=0; i<m; i++) {
        cin >> a >> b;
        lst[a].push_back(b);
        lst[b].push_back(a);
    }
    

    // 1부터 모든인원 bfs돌리기.
    for(int i=1; i<=n; i++) {
        // visited 초기화
        fill(&visited[0], &visited[0] + 101, 0);
        // i부터 n까지 
        go(i);
    }
    
    
    // for(pair<int, int> i: result) {
    //     cout << i.first << "번째  " << i.second << "\n";
    // }
    
    sort(result.begin(), result.end(), comp);
    // for(pair<int, int> i: result) {
    //     cout << i.first << "번째  " << i.second << "\n";
    // }
    
    cout << result.front().first << "\n";
    return 0;
}