[Python] 1389번 케빈 베이컨의 6단계 법칙

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

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

---

 

22/12/05

 

 

플로이드-워셜이나 BFS응용으로 풀 수 있는 문제로, BFS응용풀이에 대한 아이디어는 14217번과 같은 아이디어를 공유하고 있다.

 

2022.11.29 - [백준 문제 풀이] - [Python] 14217번 그래프 탐색

[Python] 14217번 그래프 탐색

---

 

문제 접근 방식:

 

 

1. BFS응용으로 푸는 방법

 

14217번에서 나온 아이디어를 활용하여, BFS를 한 번 진행할 때 visited배열에 현재 방문한 시간을 기록해준다.

 

이후 visited배열을 sum해주면 그 사람의 베이컨 넘버를 구할 수 있기 때문에, 모든 사람에 대해서 BFS를 돌려준다. 

 

BFS를 노드 개수만큼 돌려서 구하기 때문에, 시간 복잡도 $O(N^2+NM)$로 문제를 해결할 수 있다.

 

 

2. 플로이드-워셜로 푸는 방법

 

플로이드-워셜로 모든 쌍에 대한 최단 거리를 구한 뒤, 그 최단 거리를 한 사람에 대해서 다 더해준다면 그 사람에 대한 베이컨 넘버를 구할 수 있다.

 

플로이드-워셜로 접근한다면 시간 복잡도 $O(N^3)$로 문제를 해결할 수 있다.

 

 

이 문제의 경우, $N$의 최대 제한이 $100$, $M$의 최대 제한이 $5000$이기 때문에 BFS응용으로 푸는 것이 더 빠르다.

 

하지만 개인적으로 플로이드-워셜을 연습하기에 굉장히 훌륭한 문제라고 생각한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1389번 케빈 베이컨의 6단계 법칙
# 그래프 이론, 그래프 탐색, BFS
import sys
from collections import deque
input = sys.stdin.readline

def BFS(graph, start):
    knowing_bridges = [-1 for _ in range(N+1)]
    queue = deque()
    queue.append((start, 0))
    knowing_bridges[start] = 0
    knowing_bridges[0] = 0
    while queue:
        me, step = queue.popleft()
        for friend in graph[me]:
            if knowing_bridges[friend] == -1:
                knowing_bridges[friend] = step+1
                queue.append((friend, step+1))
    return sum(knowing_bridges)

N, M = map(int, input().rstrip().split())  # 유저의 수, 친구 관계의 수
graph = [[] for _ in range(N+1)]
for _ in range(M):
    friend1, friend2 = map(int, input().rstrip().split())
    graph[friend1].append(friend2)
    graph[friend2].append(friend1)

min_person = 1
min_bacon_num = BFS(graph, 1)
for person in range(2, N+1):
    bacon_num = BFS(graph, person)
    if bacon_num < min_bacon_num:
        min_bacon_num = bacon_num
        min_person = person
print(min_person)

# 1389번 케빈 베이컨의 6단계 법칙
# 그래프 이론, 그래프 탐색, 플로이드-워셜
import sys
input = sys.stdin.readline
INF = sys.maxsize

N, M = map(int, input().rstrip().split())  # 유저의 수, 친구 관계의 수
graph = [[INF for _ in range(N)] for _ in range(N)]
for _ in range(M):
    friend1, friend2 = map(int, input().rstrip().split())
    graph[friend1-1][friend2-1] = 1
    graph[friend2-1][friend1-1] = 1

for mid_person in range(N):
    for start_person in range(N):
        for end_person in range(N):
            if start_person == end_person:
                graph[start_person][end_person] = 0
            else:
                graph[start_person][end_person] = min(graph[start_person][mid_person]+graph[mid_person][end_person],
                                                      graph[start_person][end_person])
min_person = 0
min_bacon_num = sys.maxsize
for person in range(N):
    bacon_num = sum(graph[person])
    if bacon_num < min_bacon_num:
        min_bacon_num = bacon_num
        min_person = person

print(min_person+1)