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

1. 문제

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

2. 개요

사람 수와 친구 관계가 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

플로이드 워셜을 이용해 각 사람과의 단계를 구한 뒤, 뒤쪽부터 케빈 베이컨의 수를 확인한다.

지금까지 구한 수보다 같거나 작다면 답을 갱신해나가고 탐색을 끝마쳤다면 이를 출력한다.

3-2. Python

import sys

N, M = map(int, sys.stdin.readline().split())

answer = N-1
maxvalue = 10000

graph = [[maxvalue for i in range(N)] for j in range(N)]

for i in range(N):
    graph[i][i] = 0

for i in range(M):
    a, b = map(int, sys.stdin.readline().split())

    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

for m in range(N):
    for s in range(N):
        for e in range(N):
            if graph[s][e] > graph[s][m] + graph[m][e]:
                graph[s][e] = graph[s][m] + graph[m][e]

for i in range(N-1, -1, -1):
    if sum(graph[i]) <= maxvalue:
        maxvalue = sum(graph[i])
        answer = i+1

print(answer)

3-3. C#

namespace boj_1389
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            int answer = N - 1;
            List<List<int>> graph = new List<List<int>>();

            int maxvalue = 10000;

            for (int i = 0; i < N; i++)
            {
                graph.Add(Enumerable.Repeat(maxvalue, N).ToList());
                graph[i][i] = 0;
            }

            for (int i = 0; i < M; i++)
            {
                string[] info = sr.ReadLine().Split();
                int a = int.Parse(info[0]);
                int b = int.Parse(info[1]);

                graph[a - 1][b - 1] = 1;
                graph[b - 1][a - 1] = 1;
            }

            for (int m = 0; m < N; m++)
            {
                for (int s = 0; s < N; s++)
                {
                    for (int e = 0; e < N; e++)
                    {
                        if (graph[s][e] > graph[s][m] + graph[m][e])
                            graph[s][e] = graph[s][m] + graph[m][e];
                    }
                }
            }

            for (int i = N - 1; i > -1; i--)
            {
                if (graph[i].Sum() <= maxvalue)
                {
                    maxvalue = graph[i].Sum();
                    answer = i + 1;
                }
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}