알고리즘 스터디 - 백준 1389번 : 케빈 베이컨의 6단계 법칙

문제 해석

• 케빈 베이컨의 법칙은 지구에 있는 모든 사람들이 최대 6단계 이내 서로 아는 사람으로 연결될 수 있다는 것이다.
• 여기에서의 케빈 베이컨의 수는 모든 사람과 연결했을 때 나오는 단계의 합이라고 할 수 있다.
• 5명이 있을 때 케빈 베이컨의 수가 가장 작은 사람을 구하는 것이다.

입력

1. 유저의 수 N, 친구 관계의 수 M
2. M개의 줄에 친구 관계가 나오게 됨

알고리즘 코드

• BFS로도 할 수 있지만 최단 경로를 구하기 위해 플로이드 워셜 방법을 사용해봤다.

N, M = map(int,input().split())

INF = int(1e9)

graph = [[0] * (N+1) for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int,input().split())
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1, N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
            # 시작점과 끝점이 같으면 안됨 
            if j != k and graph[j][i] and graph[i][k]:
                if graph[j][k] == 0:
                    graph[j][k] = graph[j][i] + graph[i][k]
                else:
                    graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

result = [sum([graph[i][j] for j in range(1, N+1)]) for i in range(1, N+1)]
print(result.index(min(result)) + 1)