[알고리즘][Python] 백준 1389 케빈 베이컨의 6단계 법칙 문제 풀이

문제 출처 :www.acmicpc.net/problem/1389

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

---

문제 해석 : 사람들끼리 몇 다리를 거치면 알고 있는가를 구하는 문제입니다. 즉 그래프로 생각했을 때 이동할 수 있는 경로, 간선 들이 존재하는지 그리고 그 길이가 얼마인지를 계산하는 문제입니다.

 

문제 풀이 :  모든 사람들에 대해서 계산을 해야하므로 플로이드 - 워셜 알고리즘을 사용하면 풀 수 있습니다.

플로이드 - 워셜 알고리즘은 

 

for k in range(N):

    for a in range(N):

        for b in range(N):

            relation[a][b] = min(relation[a][b], relation[a][k] + relation[k][b])

 

다음과 같이 모든 경우를 체크하면서 최솟값을 업데이트해주는 알고리즘입니다.

---

풀이 코드

INF = int(1e9)

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

relation = [[INF] * N for _ in range(N)]

for i in range(N):
    relation[i][i] = 0

for _ in range(M):
    start, end = map(int, input().split())
    relation[start-1][end-1] = 1
    relation[end-1][start-1] = 1
    
for k in range(N):
    for a in range(N):
        for b in range(N):
            relation[a][b] = min(relation[a][b], relation[a][k]+relation[k][b])

answer = INF
index = INF
for i in range(len(relation)):
    if sum(relation[i]) < answer:
        answer = sum(relation[i])
        index = i
print(index+1)

 

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.