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

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

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

bfs 를 이용하여 문제를 해결하였습니다.

• 인접리스트를 이용하여 각 유저간의 연결 관계를 표시합니다.

  for (int i=0;i<M;i++){
    int n1, n2;
    cin >> n1 >> n2;
    v[n1].push_back(n2);
    v[n2].push_back(n1);
  }
  

• 각 유저마다 bfs 를 통해 케빈 베이컨의 수 를 계산하여 그 값 중 최솟값을 출력합니다.

• bfs 에서 케빈 베이컨의 수 를 계산하기 위해 visited 배열을 이용하였습니다. visited 배열은 -1로 초기화하여 -1일 경우 방문하지 않은 노드로 확인을 했습니다. 또한 visited[i] 의 값은 start 노드로 부터 i 번째 노드까지의 다리의 개수입니다. 이를 result 에 계속 더해줌으로서 케빈 베이컨의 수 를 계산 할 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int visited[101];
vector<int> v[101];

int bfs(int start){
    queue<int> q;
    q.push(start);
    visited[start] = 0;
    
    int result = 0;
    
    while (!q.empty()){
        int now = q.front();
        q.pop();
        result += visited[now];
        for (int next:v[now]){
            if (visited[next] == -1){
                visited[next] = visited[now] + 1;
                q.push(next);
            }
        }
    }
    return result;
}

int main(int argc, const char * argv[]) {
    
    int N,M;
    cin >> N >> M;
    
    for (int i=0;i<M;i++){
        int n1, n2;
        cin >> n1 >> n2;
        v[n1].push_back(n2);
        v[n2].push_back(n1);
    }
    
    int minNum = 987654321;
    int answer = 0;
    
    for (int i=1;i<=N;i++){
        memset(visited, -1, sizeof(int)*(N+1));
        int result = bfs(i);
        if (result < minNum){
            minNum = result;
            answer = i;
        }
    }
    
    cout << answer << "\n";

    return 0;
}