[백준] 1389번 : 케빈 베이컨의 6단계 법칙 (Python)

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

 

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.

케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

 

이 문제는 가장 작은 케빈 베이컨을 가지는 유저를 찾는 문제다.

 

 

플로이드 워셜 알고리즘 사용

import sys
from queue import PriorityQueue

input = sys.stdin.readline

N, M = map(int, input().split()) # 유저의 수 N, 친구 관계의 수 M

rel = [[sys.maxsize for _ in range(N+1)] for _ in range(N+1)] # 인접 행렬
    
# 인접 행렬을 matrix 행렬에 저장
for i in range(M):
    a, b = map(int, input().split())
    rel[a][b] = 1
    rel[b][a] = 1

# 플로이드-워셜 알고리즘 수행
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):

            if(i==j): # 같은 사람에게 0 저장
                rel[i][i] = 0
                continue
            
            rel[i][j] = min(rel[i][j], rel[i][k]+rel[k][j]) # 관계 구하기
            
# max_size 0으로 대체
for row in range(N+1):
    for col in range(N+1):
        if rel[row][col] == sys.maxsize:
            rel[row][col] = 0

# 케빈 베이컨 구하기
que = PriorityQueue() # 우선순위 큐 생성

for i in range(1, N+1):
    que.put((sum(rel[i]), i)) # 유저 번호와 케빈 베이컨의 값 넣기
print(que.get()[1]) # 케빈 베이컨의 수가 가장 작은 사람 추출

 

가장 작은 케빈 베이컨을 가지는 유저를 구하기 위해선, 각 유저의 다른 모든 유저간의 케빈 베이컨의 값을 알아야 한다.

즉, 모든 유저 A, B간의 A에서 B로 가는 경로를 알아야 하며, 이는 플로이드-워셜 알고리즘을 사용하면 구할 수 있다.

** BFS 등의 탐색 알고리즘을 사용해서도 구할 수 있음!

 

1. 유저 간의 관계를 인접행렬에 저장
2. 플로이드-워셜 알고리즘 사용해 관계도 구하기
3. 우선순위 큐를 사용해 가장 작은 케빈 베이컨의 수를 갖는 유저 번호 구하기

 

이를 통해서 가장 작은 케빈 베이컨의 수를 갖는 유저 번호를 구할 수 있다!

 

 

 

BFS 사용

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())  # 유저의 수 N, 관계의 수 M
tree = [[] for i in range(N+1)]  # 인접 리스트

# 트리 저장
for _ in range(M):
    a, b = map(int, input().split())

    # 양방향 저장
    tree[a].append(b)
    tree[b].append(a)

# BFS 구현
def BFS(start):
    q = deque([start])
    depth[start] = 1  # 최초 노드 depth 1

    while q:
        now = q.popleft()

        for i in tree[now]:
            if not depth[i]:  # 미방문 노드일 때
                depth[i] = depth[now] + 1 # 깊이 저장
                q.append(i) # 자식 노드 저장

# 케빈 베이컨 구하기
max_ = float('inf') # 최대 케빈 베이컨의 값 
user = 0 # 유저 번호

for i in range(1, N+1):
    depth = [0] * (N+1)  # 깊이 배열 생성
    BFS(i) # 거리 구하기

    if(max_ > sum(depth)): # 작은 케빈 베이컨 수 발견시
        max_ = sum(depth) # 최솟값 저장
        user = i # 유저 저장

print(user) 

 

BFS, 너비 우선 탐색을 사용해서 구할 수도 있다.

유저 A로부터 다른 모든 유저로 가는 경로의 깊이, depth를 구해 케빈 베이컨의 값을 얻을 수 있음!

 

1. 유저 간의 관계를 인접 리스트에 저장

2. BFS를 사용해 각 유저간의 거리 구하기

3. 우선순위 큐를 사용해 가장 작은 케빈 베이컨의 수를 갖는 유저 번호 구하기