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

문제 링크

플로이드워셜 알고리즘을 사용하여, i에서 j까지 몇 단계만에 연결될 수 있는지 계산하는 문제

본인과의 관계는 0단계, 친구 관계는 1단계만에 이어진다. 친구 관계를 이용하여 모든 사람간의 단계수를 계산하면 된다.

예를 들어 친구의 친구는 나와 2단계로 이어진다.
(나 - 친구 - 친구의친구)

[제출한 코드]

INF = int(1e9) # 무한을 의미하는 값

n, m = map(int, input().split()) # 유저 수, 친구 관계 수
result = [] # 각 유저의 케빈 베이컨 수를 저장할 리스트

graph = [[INF] * (n + 1) for _ in range(n + 1)] # 그래프 초기화

# 자기 자신과는 0단계만으로 알 수 있으므로 0으로 초기화
for i in range(n + 1):
    for j in range(n + 1):
        if i == j:
            graph[i][j] = 0
            

# 친구 관계는 1단계만으로 알 수 있으므로 1로 초기화
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
    
# 플로이드워셜 알고리즘을 활용해 몇단계 만에 서로를 알 수 있는지 계산
for k in range(1, n + 1): # 경유 정점
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 각 유저별 케빈 베이컨 수 계산
for i in range(1, n + 1):
    result.append((sum(graph[i]), i))

# 케빈 베이컨 수를 기준으로 오름차순 정렬
result.sort()
print(result[0][1])