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

최단 경로 알고리즘

 

 

Q

 

www.acmicpc.net/problem/1389

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

 

A

 

플로이드 워셜 알고리즘을 이용하여 풀었다. 

 

코드

INF = int(1e9)

n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(n + 1):
    for b in range(n + 1):
        if a == b:
            graph[a][b] = 0
            
for _ in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1 #양방향일때는 이거 빼먹으면 안된다!!

for k in range(n + 1): #플로이드 워셜 알고리즘 실행
    for i in range(n + 1):
        for j in range(n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
            
sum_list = [0] * (n + 1)
for i in range(n + 1):
    for j in range(n + 1):
        if graph[i][j] < INF:
            sum_list[i] += graph[i][j]

result = INF
for k in sum_list:
    if k != 0:
        result = min(result, k) #케빈 베이컨 수가 작은 사람의 값 찾기

 

print(sum_list.index(result)) #값에 해당하는 인덱스 위치 찾아서 출력