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

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

1. 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<int>> userGraph(N + 1);

    // 친구 관계 입력
    for (int i = 0; i < M; ++i)
    {
        int u, v;
        std::cin >> u >> v;

        userGraph[u].push_back(v);
        userGraph[v].push_back(u);
    }

    std::vector<int> distance(N + 1);
    std::queue<int> userQueue;
    int minSum = N * N;
    int ansUser = 0;
    
    for (int user = 1; user <= N; ++user)
    {
        std::fill(distance.begin() + 1, distance.end(), -1);
        distance[user] = 0;
        userQueue.push(user);

        // BFS로 최단 거리 업데이트
        while (!userQueue.empty())
        {
            int u = userQueue.front();
            userQueue.pop();

            for (int v : userGraph[u])
            {
                if (distance[v] == -1)
                {
                    distance[v] = distance[u] + 1;
                    userQueue.push(v);
                }
            }
        }

        int sum = 0;
        // 케빈 베이컨의 수 계산
        for (int i = 1; i <= N; ++i)
        {
            sum += distance[i];
        }

        // 케빈 베이컨의 수가 가장 작은 경우
        if (sum < minSum)
        {
            minSum = sum;
            ansUser = user;
        }
    }

    std::cout << ansUser;

    return 0;
}

2. 분석

BFS를 활용해 최단 거리를 구하는 것이 핵심인 문제였습니다. 최단 거리를 구하기 위해 userGraph, distance, userQueue를 사용합니다. 유저 A로부터 다른 모든 유저의 최단 거리를 구하려고 할 때 다음과 같이 진행됩니다.

모든 유저의 distance를 -1로 설정합니다.
유저 A의 distance는 0으로 설정하고 userQueue에 유저 A를 넣습니다
BFS 반복문에 진입합니다.
userQueue에서 유저 한 명을 꺼내고, userGraph를 이용해서 꺼낸 유저에 연결된 유저들을 조사합니다.
연결된 유저의 distance가 -1이면 최단 거리를 계산하고, -1이 아니면 최단 거리를 이미 계산한 것으로 간주합니다.
최단 거리를 계산할 때 유저 u → 유저 v라고 하면, 유저 v의 최단 거리를 distance[u] + 1로 계산합니다. 계산 후 유저 v는 큐에 넣습니다.
큐에 유저가 없을 때까지 BFS 반복문이 진행됩니다.

위와 같은 과정으로 최단 거리를 구한 후 케빈 베이컨 수를 계산합니다. 가장 작은 케빈 베이컨 수라면 정답에 해당하는 유저를 업데이트합니다. 시간 복잡도를 계산하겠습니다. 유저 한 명의 케빈 베이컨 수를 계산할 때 userGraph에 BFS를 수행합니다. BFS를 수행하면, 모든 정점을 한 번씩 방문하고 방문 시 연결된 간선을 순회합니다. 따라서 유저 한 명의 케빈 베이컨 수를 구할 때 시간 복잡도는 O(N + M)입니다. 모든 유저의 케빈 베이컨 수를 구하기 때문에 모든 유저에 대해 BFS를 수행합니다. 이것까지 고려하면 최종 시간복잡도는 O(N * (N + M))입니다.

1. 코드#

2. 분석#

1. 코드

2. 분석