백준 1389. 케빈 베이컨의 6단계 법칙

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

1. BFS 풀이

# 모든 사람과의 거리가 제일 적은 사람 구하기!
# 여러 명이면 번호가 가장 작은 사람

from collections import deque

n, m = map(int,input().split()) # 유저 수, 친구관계 수
dp= [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int,input().split())
    dp[a].append(b)
    dp[b].append(a)
dist = [[0] * (n+1) for _ in range(n+1)]


for i in range(1, n+1):
    q = deque([i])
    visited = [0] *(n + 1)
    visited[i] = 1
    while q:
        node, d = q.popleft()
        for friend in dp[node]:
                if visited[friend] == 0:
                    visited[friend] = 1
                    dist[i][friend] = dist[i][node] + 1 # 이전거리 +1 
                    q.append(friend)

min_sum = float('inf')
ans = 0
for i in range(1, n + 1): # 1부터 n까지 케빈 베이컨 수 더해서 정답 찾을 것!
    total_distance = sum(dist[i][1:])  # 사람 i의 케빈 베이컨 수(0은 의미없으니 1부터)
    if total_distance < min_sum:
        min_sum = total_distance
        ans = i
    elif total_distance == min_sum and i < ans: # 예외처리
        ans = i

print(ans)

2. 플로이드-워셜 풀이

# 모든 사람과의 거리가 제일 적은 사람 구하기!
# 여러 명이면 번호가 가장 작은 사람

from collections import deque

n, m = map(int,input().split()) # 유저 수, 친구관계 수
dp= [[float('inf')]*(n+1) for _ in range(n+1)]

# 본인에서 본인으로의 거리는 0으로 설정
for i in range(1, n + 1):
    dp[i][i] = 0

for i in range(m):
    a, b = map(int,input().split())
    dp[a][b] = 1
    dp[b][a] = 1

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

min_sum = float('inf')
answer = 0
for i in range(1, n + 1):
    total_distance = sum(dp[i][1:])  # 사람 i의 케빈 베이컨 수
    if total_distance < min_sum:
        min_sum = total_distance
        answer = i
    elif total_distance == min_sum and i < answer: # 예외처리
        answer = i

print(answer)