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

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 플로이드 워셜 알고리즘

개념 :: http://www.crocus.co.kr/536

소스 코드 :: http://www.crocus.co.kr/537

결국 모든 사람들이 몇단계를 거쳐 알고있는지 알아야 하기 때문에

플로이드 워설 알고리즘으로 접근 할 수 있다. 또한 사람 수가 최대 100명이기에 

플로이드 워셜 알고리즘의 O(|V|^3)에 의하면 100만번이 최악의 경우이기에 시간 복잡도 면에서도 가능하다.

플로이드 워셜의 개념 및 소스 코드를 보고 이 문제를 풀면 좋을 것 같다.(문제만 길지 사실상 매우 기본 문제이다.)

소스 코드 : 

#include <stdio.h>
#include <limits.h>
 
// 정점의 수를 지정한다.
int V;
 
// INF를 무한대라고 지정하고, INT_MAX를 이용한다.
#define INF 10000
 
int ans[101];
 
// 플로이드 워셜의 결과를 출력하는 함수
void printSolution(int dist[][101])
{
    for(int i = 1; i <= V; i ++)
        for (int j = 1; j <= V; j++)
            if (dist[i][j] != INF)
                ans[i] += dist[i][j];
 
    
    int minVal = INF;
    int minNum;
 
    for (int i = 1; i <= V; i++)
    {
        if (ans[i] < minVal)
        {
            minVal = ans[i];
            minNum = i;
        }
    }
 
    printf("%d", minNum);
}
 
 
// 모든 경로에 대한 최단 거리를 찾아주는 플로이드 워셜 함수
void floydWarshall(int graph[][101])
{
    /*
    dist[][] 배열에 최단 거리에 대한 정보들이 모두 들어가게 된다.
    */
    int i, j, k;
 
    int dist[101][101];
 
    /*
    dist[][] 배열에 초기값은 그래프에서 주어진 값들이다.
    (즉, 아직 최단 거리를 구하기 전에는 기존의 거리를 최단 거리라 생각한다.)
    */
    for (i = 1; i <= V; i++)
        for (j = 1; j <= V; j++)
            dist[i][j] = graph[i][j];
 
 
 
    /*
    플로이드 워셜 알고리즘의 핵심
    */
    // 한 점을 경유하여
    for (k = 1; k <= V; k++)
    {
        // x에서
        for (i = 1; i <= V; i++)
        {
            // y로 갈때
            for (j = 1; j <= V; j++)
            {
                // 최단거리면 업데이트 해준다.
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
 
    // 모든 최단거리가 구해지고 난 뒤, 출력을 해준다.
    printSolution(dist);
}
 
 
int main()
{
 
    int graph[101][101];
    int from, to, n;
 
    scanf("%d", &V);
    scanf("%d", &n);
 
    for (int i = 1; i <= V; i++)
        for (int j = 1; j <= V; j++)
            i == j ? graph[i][j] = 0 : graph[i][j] = INF;
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &from, &to);
        graph[from][to] = 1;
        graph[to][from] = 1;
    }
 
    // 플로이드 워셜 알고리즘으로 진입
    floydWarshall(graph);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>