Algorithm/Baekjoon

[Algorithm] Baekjoon 1389번 : 케빈 베이컨의 6단계 법칙

MaxLevel 2022. 10. 19. 17:40

https://www.acmicpc.net/problem/1389

 

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

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻

www.acmicpc.net

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
int graph[101][101];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    memset(graph, 0x3f, sizeof(graph));
 
    int vc;
    int ec;
    int first;
    int second;
 
    cin >> vc >> ec;
 
    for (int i = 1; i <= vc; i++)
    {
        graph[i][i] = 0;
    }
 
    for (int i = 0; i < ec; i++)
    {
        cin >> first >> second;
        graph[first][second] = 1;
        graph[second][first] = 1;
    }
    
    for (int k = 1; k <= vc; k++)
    {
        for (int i = 1; i <= vc; i++)
        {
            for (int j = 1; j <= vc; j++)
            {
                if (graph[i][k] + graph[k][j] <= graph[i][j])
                {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
 
    int answer = 10000000;
    int minIndex = 0;
 
    for (int i = 1; i <= vc; i++)
    {
        int sum = 0;
 
        for (int j = 1; j <= vc; j++)
        {
            sum += graph[i][j];
        }
 
        if (sum < answer)
        {
            answer = sum;
            minIndex = i;
        }
    }
 
    cout << minIndex;
 
    return 0;
}
 cs

 

각 정점에서 다른 정점까지의 최소거리만 구하면 되는 문제이다.

BFS로 각 정점을 다 돌려도 되고, 위 코드처럼 플로이드와샬로 풀어도된다.