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

1.문제

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

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

 

2. 접근

1. 문제에서 n(node)과 m(edge)가 주워졌으며, 친구관계가 양방향이고 n의 범위가 500이하라는 점에서 플로이드를 떠올릴 수 있었다.

2. 친구가 연결되는 관계수가 적으며, 동일한 관계수일 경우에는 작은 인덱스 값을 뽑기 위해서 ( i -> j ) 이동하는 관계에서 cnt 변수에 더해져 가는 관계의 수를 더하고 그 값과 인덱스를 하나의 배열에 같이 저장을 시켰다

3. 마지막에 ( 관계의 총합 수 -> 인덱스 ) 순서로 정렬을 통해서 답을 구해줬다

 

 

3. 풀이

# 1389
import sys
input = sys.stdin.readline

INF = int(1e9)
n , e= map(int,input().split())

graph = [[INF] *(n+1) for _ in range(n+1)]

# 양방향
for i in range(e):
    a,b = map(int,input().split())
    graph[a][b] = 1
    graph[b][a] = 1

# 자기 자신으로 이동은 값이 0 이다
for i in range(1,n+1):
    graph[i][i] = 0

# 최소 거리 구하자
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

res = []
for i in range(1,n+1):
    cnt = 0 # 관계의 수를 더해줄것
    for j in range(1,n+1):  
        cnt += graph[i][j]
    res.append([cnt,i])

res.sort(key=lambda x:(x[0],x[1]))
print(res[0][1])