[#알고리즘/최단 경로/[백준]1389번: 케빈 베이컨의 6단계 법칙(python)]

Question

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

Solution

1. 입력으로 받은 친구 관계에 대해, 친구이면 1로 설정을 한다.
2. 플로이드 워셜 알고리즘을 수행하여 단계를 거쳐 아는 사이가 되는 관계를 찾아 정보를 갱신한다. (단계 값을 갱신)
3. 각 유저의 케빈 베이컨 수 중 최솟값을 가지는 유저의 번호를 출력한다.

Code

import sys

input = sys.stdin.readline
INF = int(1e9)

# 유저의 수 n, 친구 관계의 수 m
n, m = map(int, input().split())

# 2차원 리스트를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 친구 관계이면 1로 설정
for _ in range(m) :
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
    
# 자기 자신에서 자신으로 가는 비용은 0
for a in range(1, n + 1) :
    for b in range(1, n + 1) :
        if a == b :
            graph[a][b] = 0

# 플로이드 워셜 알고리즘 수행 (건너 건너 친구 관계이면 1로 설정)
for k in range(1, n + 1) :
    for a in range(1, n + 1) :
        for b in range(1, n + 1) :
           graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
          

min = 1000
answer = 0
for a in range(1, n + 1) :
    sum = 0
    for b in range(1, n + 1) :
        if graph[a][b] > 0 and graph[a][b] != INF :
            sum += graph[a][b]
    if sum < min :
        min = sum
        answer = a
        
print(answer)