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

2024.03.25 - [CS/Algorithm] - [알고리즘 개념 정리] 플로이드 워셜 (Python)

플로이드 워셜을 학습한 뒤 풀은 플로이드 워셜을 활용하는 문제를 풀었다 🐥

 

문제 링크

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

 

문제 요약

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

케빈 베이컨의 수란, 한 사람이 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합을 의미한다.

백준 유저 사이에서 케빈 베이컨의 수가 가장 작은 사람을 찾아 출력하는 것이 목표다.

    (만약, 그런 사람이 여러 명이면 번호가 가장 작은 사람을 출력)

 

유저의 수 n과 친구 관계의 수 m이 주어진다.

이어서 m개의 줄에 걸쳐 친구 관계가 주어지며 a, b가 친구라는 정보가 주어진다. (친구 관계는 양방향이다)

 

접근 방법 정리

1. 2차원 배열로 INF(무한을 의미하는 수)로 초기화

2. 자기 자신 -> 자기 자신으로 가는 경우 0으로 초기화

3. 주어진 친구 관계는 1단계 만에 연결되기 때문에 1로 초기화 (양뱡향)

4. 플로이드 워셜을 활용해 기존 값과 k를 거쳐가는 값 중 최솟값으로 초기화

5. 각 사람 별 케빈 베이컨 수 합 구한 후 가장 작은 값의 인덱스 출력하기

 

코드

import sys
input = sys.stdin.readline

INF = int(1e9)
n, m = map(int, input().split())
arr = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            arr[a][b] = 0

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

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            arr[a][b] = min(arr[a][b], arr[a][k] + arr[k][b])

results = [0] * n
for i in range(1, n + 1):
    sum = 0
    for j in range(1, n + 1):
        sum += arr[i][j]
    results[i - 1] = sum

print(results.index(min(results)) + 1)