[Baekjoon] 1389. 케빈 베이컨의 6단계 법칙

🔗 Problem Link

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

---

❔Thinking

• N명의 사람에 대한 친구관계가 주어질 때, 베이컨 법칙에 따른 총합이 제일 적은 사람을 반환한다.

---

💻Solution

1. 플로이드-워셜을 활용한 풀이

import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

# 친구관계 입력
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

# 케빈 베이컨 계산 (플로이드-워셜)
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

# 케빈 베이컨 총합이 가장 작은 사람
bacon = INF
result = 0
for i in range(1, n+1):
    tmp = sum(graph[i][1:])
    if bacon > tmp:
        bacon = tmp
        result = i

print(result)

 

2. DFS(깊이 우선 탐색)을 활용한 풀이

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
result_u = 0
result_bacon = INF

friends = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)

for u in range(1, n+1):
    bacon = {u:0}
    q = deque([u])
    while q:
        now = q.popleft()
        for next_u in friends[now]:
            if next_u not in bacon:
                bacon[next_u] = bacon[now]+1
                q.append(next_u)
    now_bacon = sum(bacon.values())
    if result_bacon > now_bacon:
        result_bacon = now_bacon
        result_u = u

print(result_u)

---

🗝️keypoint

1. N이 100이하로 작기 때문에, 플로이드-워셜을 활용한 풀이가 가능하다.
2. N명의 사람이 자기 자신을 제외한 다른 모든 사람과의 몇 단계를 통해 이어지는지 확인하는것이 중요하다.