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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1389번 케빈 베이컨의 6단계 법칙
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

사람 간 친구 관계 그래프가 주어질 때, 각 사람의 케빈 베이컨 수(다른 모든 사람까지 최단거리 합)를 계산해 가장 작은 사람 번호를 출력하는 문제입니다.

코드

import sys;read=sys.stdin.readline
from collections import deque

# 입력
n,m=map(int,read().split())
d=[[0]*n for _ in range(n)] # d[a-1][b-1] = d[b-1][a-1] = a와 b의 친구 단계

for i in range(m):
    a,b=map(int,read().split())
    d[a-1][b-1] = d[b-1][a-1] = 1

# print(d)

# BFS 준비
q=deque([])
enQ=q.append
deQ=q.popleft

# BFS
for i in range(n):
    q.clear()
    visited = [False]*n
    enQ((i,0))
    visited[i] = True
    
    while q:
        j,lv=deQ()
        for k in range(n):
            if not visited[k] and d[j][k] == 1:
                d[i][k] = d[k][i] = lv+d[j][k]
                enQ((k,lv+d[j][k]))
                visited[k] = True
# print(d)

r = list(map(sum,d))
print(r.index(min(r))+1)

설명

각 정점을 시작점으로 BFS를 수행해 다른 정점까지의 최단 거리를 채웁니다.

모든 정점에 대해 거리 합을 구하고, 최솟값의 인덱스(1-based)를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---