백준 1389 케빈 베이컨의 6단계 법칙 c++ [컴공과고씨]

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

1389번: 케빈 베이컨의 6단계 법칙

 

문제 정리

1. 유저가 번호로 주어짐

2. 관계가 주어짐. 관계라는 것은 예를 들어 1 2 이렇게 주어지면 1과 2는 연결되어 있다는 것을 말함.

3. 관계가 1 2 주어지고 2 4 로 주어진다고 치면 1에서 4로 갈때의 단계는 1 2(1단계) 2 4(2단계)

그래서 총 2단계를 걸처 1에서 4가 연결되어 있다고 함.

이 때 다른 사람과의 관계의 총 합을 케빈 베이컨의 수라고 함.

케빈 베이컨의 수가 가장 적은 수의 사람을 출력해라. 같은 케빈 베이컨의 수가 있을 경우 가장 작은 번호의 사람을 출력하라.

 

문제 해결 방법

bfs를 이용하여 사람 마다 다른 사람까지 가는데 걸리는 단계를 측정한다.

그 단계들을 합해준다.

그 후 다음 사람과 다른 사람까지의 단계를 측정해 케빈 베이컨 수를 구해 전에 측정해준 값과 비교하여 더 작은 값을 저장해준다.

bfs 같은 경우 기본 bfs와 같다.

코드 주석을 보면 이해가 쉽게 될 것입니다.

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<int> v[102];
int a, b;
int count = 0; // 시작 사람에서 목표 사람 까지의 단계 수
void bfs(int a,int b, bool visit[102]){
    queue<pair<int, int>> q;
    q.push(make_pair(a,0));
    visit[a] = true;
    while(!q.empty()){
        int x = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if(x == b){
            count = cnt;
            break;
        }
 
        for (int i = 0; i < v[x].size(); i++){
            if(!visit[v[x][i]]){
                q.push(make_pair(v[x][i], cnt+1));
                visit[v[x][i]] = true;
            }
        }
    }
}
 
int main(){
    cin >> n >> m;
    for (int i = 0; i < m;i++){
        cin >> a >> b;
        v[a].push_back(b); // 사람 관계는 양방향임.
        v[b].push_back(a);
    }
    int result = 98765432; // 케빈 베이컨의 수
    int num; // 케빈 베이컨의 수에 해당하는 사람 번호
    for (int i = 1; i <= n;i++){ // 시작하는 사람
        int temp = 0; // 한 사람이 다른 사람까지 가는 단계
        for (int j = 1; j <= n;j++){ // 목표사람
            bool visit[102] = {0}; 
            if(i==j) // 시작 사람과 목표 사람이 같은 경우 넘김
                continue;
            bfs(i, j, visit); 
            temp += count; // 각 목표 사람의 단계를 모두 합쳐 케빈 베이컨의 수를 구함
            count = 0; // 목표 사람의 단계 초기화
        }
        if(result > temp){ // 전의 케빈 베이컨의 수와 비교하여 더 작은 값을 저장
            result = temp;
            num = i;
        }
            
    }
    cout << num << '\n';
    return 0;
}