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

 

문제 링크 https://www.acmicpc.net/problem/1389

KEY

• N번까지의 노드를 하나씩 출발노드로 지정하면서 (노드, 이동거리)의 큐를 만들어 이동거리의 합을 구하면 된다.

테스트케이스에서 예를 들어보면 다음과 같다.

• 1번노드에서 출발했을 때 1번(1,0) -> 3번(3,1), 4번(4,1) -> 2번(2,2), 5번(5,2)
• 따라서 이동거리의 총 합은 0+1+1+2+2 = 6
• 이 과정을 1~N노드까지 반복수행 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 101;
int N, M;
vector<vector<int>> v;
vector<int> result;
bool visited[MAX];
int sum;
int mins = 1000000000;  
int answer; 
 
int bfs(int start) {
    visited[start] = true;
    sum = 0; //거리의 총합 변수
    queue<pair<int, int>> q; //(노드, 이동거리)로 저장
    q.push({ start,0 }); 
 
    while (!q.empty()) {
        int node = q.front().first;
        int dist = q.front().second;
        sum += dist; //거리를 다 더한다.
        q.pop();
        for (int i = 0; i < v[node].size(); i++) {
            int next = v[node][i];
            if (visited[next])
                continue;
            visited[next] = true;
            q.push({ next,dist + 1 });
        }
    }
    return sum;
}
int main(void) {
    cin >> N >> M;
    v.resize(N + 1);
    for (int i = 0; i < M; i++) {
        int first, second;
        cin >> first >> second;
        v[first].push_back(second);
        v[second].push_back(first);
    }
 
    for (int i = 1; i < v.size(); i++) {
        memset(visited, false, sizeof(visited)); //방문배열 초기화
        result.push_back(bfs(i));
    }
 
    for (int i = 0; i < result.size(); i++) { //최솟값 검색
        mins = min(mins, result[i]);
    }
 
    for(int i = 0; i < result.size(); i++) { //처음으로 최솟값을 만족하는 index
        if (result[i] == mins) {
            answer = i;
            break;
        }
    }
    cout << answer + 1;
}