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

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

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>
#include <set>
#include <iomanip>
#include <string.h>
#include <sstream>
#include <tuple>
#include <regex>
#include <stack>
#include <map>

using namespace std;

vector<int> toNodes;
vector<vector<int>> friends;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m; // 유저 수, 친구 관계 수
    cin >> n >> m;

    friends = vector<vector<int>>(n + 1); // 0번 인덱스 안 써
    toNodes = vector<int>(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        friends[a].push_back(b);
        friends[b].push_back(a);
    }

    int totalTmp = INT_MAX;
    int answer = -1;
    for (int i = 1; i <= n; i++) {
        // 노드 하나마다 케빈 베이컨 수 구하기
        int nodeKebinNum = 0;

        queue<pair<int, int>> nexts;
        fill(toNodes.begin(), toNodes.end(), 0);
        
        nexts.push({ i, 1 });
        toNodes[i] = 1; 
        
        while (!nexts.empty()) {
            pair<int, int> cur = nexts.front(); nexts.pop();

            for (int next : friends[cur.first]) {
                if (toNodes[next] != 0) continue;

                nexts.push({ next, cur.second + 1 });
                toNodes[next] = cur.second + 1;
            }
        }

        for (int j = 1; j <= n; j++) {
            if (i == j) continue;

            nodeKebinNum += toNodes[j];
        }

        if (totalTmp > nodeKebinNum) {
            totalTmp = nodeKebinNum;
            answer = i;
        }
    }
    cout << answer << "\n";

    return 0;
}

 

 

처음 풀었을 때는 매 for 문 마다 toNodes = vector<int>(n+1) 로 해줬더니 메모리 초과 에러가 떴다. 그래서 이 문제를 fill 함수를 이용해서 해결했다.