[탐색/플로이드] 백준 1389 케빈 베이컨의 6단계 법칙 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

 가장 인싸친구를 찾는 문제입니다. 케빈 베이컨의 6단계 법칙은 '인적 네트워크'의 중요성을 대두할 때 많이 언급하죠. 여섯 다리(지인)만 거치면 지구촌 모든 사람과 만날 수 있다는 허상(?)의 법칙입니다. 애초에 단계를 거칠 때마다 지인이 자신의 모든 지인에게 물어보고 성실하게 답해준다는 가정이 잘못됐죠.

 

2022.02.28 - [Algorithm] - [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기

[Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기

 어쨌든, 본론으로 다시 넘어와서 이 문제는 '각 노드별 최단거리를 합친 값이 가장 적은 친구'를 찾아야 합니다.

 모든 쌍의 최단거리를 계산해야 하기 때문에, 플로이드 와샬 알고리즘을 이용합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#플로이드 와샬 알고리즘
def floyd(n, dist):
    # 최단 경로 리스트 초기화
    for via in range(n): #경유지
        for start in range(n): #출발지
            for end in range(n): #도착지
                # 경유지를 경유하는 게 더 짧다면 갱신
                if dist[start][end] > dist[start][via] + dist[via][end]:
                    dist[start][end] = dist[start][via] + dist[via][end]
    return dist

 플로이드 와샬 알고리즘을 이용해서 경유하는 거리가 더 짧다면 갱신해줍니다.

 

 

#입력
N, M = map(int, input().split()) #노드, 간선 수
graph = [[10000]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

dist = floyd(N, graph)

res = 0 #가장 작은 사람
min_score = 100000
for i, lst in enumerate(dist, 1):
    if sum(lst) < min_score:
        min_score = sum(lst)
        res = i
print(res)

 플로이드 와샬 알고리즘을 사용하기 위해, 입력받은 간선 정보를 '인접 행렬'로 저장합니다. 인접 행렬은 각 노드 간 연결정보를 담은 배열을 말합니다.

 플로이드 와샬 알고리즘으로 최단거리를 구해주고, 각 노드별 최단거리를 합해줍니다. 합한 결과가 가장 작은 친구를 출력합니다.