☁️ 문제

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

이 문제는 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 해당된다. 그래서 플로이드 워셜 알고리즘을 사용해서 문제를 해결했다!

☁️ 코드

node,edge=map(int,input().split())

INF=int(1e9)
graph=[[INF]*(node+1) for _ in range(node+1)]

for i in range(1,node+1):
    for j in range(1,node+1):
        if i==j:
            graph[i][j]=0

for _ in range(edge):
    a,b=map(int,input().split())
    graph[a][b]=1
    graph[b][a]=1


for k in range(1,node+1):
    for a in range(1,node+1):
        for b in range(1,node+1):
            graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])

friends=INF
min_idx=0
for i in range(1,node+1):
    friends_num=sum(graph[i][1:])
    if friends>friends_num:
        friends=friends_num
        min_idx=i


print(min_idx)

1번부터 5번까지의 사람들을 노드라고 생각하고 이들간의 관계를 간선이라고 생각하고 접근했다. 노드가 서로 연결된 경우(친구인 경우)는 1이라고 값을 설정하고 연결되지 않은 경우는 INF로 값을 초기화한다.
그리고 플로이드 워셜 알고리즘으로 현재 노드를 거쳐가는 모든 경로를 고려해서 값을 갱신시킨다.

그러면 최종적으로 시작노드를 기준으로 다른 노드들까지의 거리를 알 수 있다. 시작노드별 케빈 베이컨 수를 계산하여 케빈 베이컨 수가 가장 작은 사람을 출력하면 끝이다~~~