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

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

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

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;
}

 

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

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