[Backjoon] 케빈 베이컨의 6단계 법칙

C++로 그래프 탐색에 대한 문제를 연습한 적이 많지 않다. 파이썬으로 풀때와 차이점은 BFS 문제에 그래프 깊이 정보를 pair<int, int> 형식으로 queue에 넣어도 메모리 초과 문제가 발생하지 않는 것 같다(오....). 1389번 케빈 베이컨의 6단계 법칙은 양방향 인접리스트를 입력받아 그래프 노드간 거리를 구하고, 그 합계가 최소인 지점을 찾는 문제이다. DFS로 풀이하려고 했는데 문제 분류에 BFS가 되어 있어 BFS로 풀이했다. 

 

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

using namespace std;

bool visited[201] = {false};

int getLinkScore(int user, int target, map<int, vector<int>> link) {
    
    int score = 0;
    
    queue<pair<int, int>> q;
    q.push(make_pair(user, score));

    while (!q.empty()) {

        int search = q.front().first;
        int nowScore = q.front().second;
        q.pop();

        if (search == target) {
            score = nowScore;
            break;
        }

        for (auto l : link[search]) {
            if (!visited[l]) {
                q.push(make_pair(l, nowScore + 1));
            }
        }
    }

    memset(visited, false, sizeof(visited));
    return score;
}

int main() {

    int totalCount, linkCount;
    cin >> totalCount >> linkCount;

    map<int, vector<int>> link;
    for (int i = 1; i <= totalCount; i++) {
        vector<int> container;
        link[i] = container;
    }

    while (linkCount--) {
        int user, linkTarget;
        cin >> user >> linkTarget;
        link[user].push_back(linkTarget);
        link[linkTarget].push_back(user);
    }

    int answerUser = 0, baconScore = INT32_MAX;
    for (int user = 1; user <= totalCount; ++user) {
        int tmpScore = 0;
        for (int targetUser = 1; targetUser <= totalCount; ++targetUser) {
            if (user == targetUser) continue;
            int result = getLinkScore(user, targetUser, link);
            tmpScore += result;
        }

        if (baconScore > tmpScore) {
            answerUser = user;
            baconScore = tmpScore;
        }
    }

    cout << answerUser << endl;
    
}