1389 - 케빈베이커의 6단계 법칙 - BFS

문제

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

풀이전략

1. 사실상 한 노드에 다른 모든 노드로 가는 거리의 합중 가장 작은 것을 찾는 것이다.
2. 노드는 최대 100개 이고, 시간은 2초이므로 나는 모든 노드들의 거리를 BFS로 찾아 그 중 최소값을 찾을 것이다.
3. 모든 사람들은 친구로 연결되어 있다는 조건 덕분에 딱히 특별히 까다로운 조건을 세울 필요는 없다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, M;
// 이미 방문한 노드를 재방문 하지 않기 위한 배열
bool ch[101];
//  각 노드에서 다른 노드들로의 길이의 합을 저장한 배열
bool chVal[101];
// 친구 관계에 대한 정보를 저장한 배열
vector<int> a[101];
int main(){
    ios_base::sync_with_stdio(false);
    freopen("../input.txt","rt",stdin);
    
    cin >> N >>M;
    int ta, tb;
    for(int i=1; i<=M; i++){
        cin >> ta >> tb;
        a[ta].push_back(tb);
        a[tb].push_back(ta);
    }
    int res = 0;
    int resSum = 2147000000;
    for(int i=1; i<=N; i++){
    	// for문을 통해 모든 노드들을 순차적으로 한번씩 BFS를 한다.
        memset(ch, false, sizeof(ch));
        memset(chVal, false, sizeof(chVal));
        queue<pair<int, int> >q;
        ch[i] = true;
        q.push(make_pair(i, 0));
        int sum = 0;
        
        while(!q.empty()){
            int ret = q.front().first;
            int val = q.front().second;
            // 다른 노드로 가는 최단거리가 나올때마다 sum에 넣어준다.
            // 단 이미 최단거리를 구할경우 그냥 패스한다. 
            if(!chVal[ret]){
                chVal[ret] = true;
                sum += val;
            }
            q.pop();
            if(!ch[ret]) continue;
            
            for(int i=0; i<a[ret].size(); i++){
                
                if(!ch[a[ret][i]]){
                    ch[a[ret][i]] = true;
                    q.push(make_pair(a[ret][i], val+1));
                    
                }
            }
        }
        if(sum < resSum){
            res = i;
            resSum = sum;
        }
    }
    
    // cout << res << endl;

    return 0;
}

소감

문제만 케빈베이커 ~~~ 하면서 어렵게 만든거지 사실상 한 노드에서 다른노드들로 가는 최단거리들의 합을 구하는 문제이다. 문제들을 잘 해석할 줄 알아야한다.