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

문제

케빈 베이컨의 6단계 법칙

케빈 베이컨 수가 가장 작은 사람을 구하자

난이도 : Silver1

---

풀이

1. bfs로 모든 사람들에 대해 케빈 베이컨 수 계산

---

코드

import sys
from collections import defaultdict, deque

N, M = tuple(map(int, sys.stdin.readline().split()))
friends = defaultdict(list)
for _ in range(M):
    f1, f2 = tuple(map(int, sys.stdin.readline().split()))
    friends[f1].append(f2)
    friends[f2].append(f1)

def bfs(start):
    visited = [False] * N  # 방문 체크 리스트
    visited[start-1] = True
    q = deque([(start, 0)])  # (시작점, 관계 거리)
    relation = {}  # 시작 - 친구거리 저장 딕셔너리
    
    while q:
        person = q.popleft()
        relation[person[0]] = person[1]
        for friend in friends[person[0]]:  # 연결 된 친구들 확인
            if not visited[friend - 1]:  # 방문하지 않은 친구라면
                visited[friend - 1] = True  # 방문 True
                q.append((friend, person[1]+1))  # (친구 번호, 거리+1) append
    
    return sum(list(relation.values()))  # 모든 딕셔너리 value sum이 케빈 베이컨 수


kevin = {}
for i in range(1, N+1):
    kevin[i] = bfs(i)

kevin = sorted(kevin.items(), key=lambda x: (x[1], x[0]))  # 케빈 베이컨 수가 가장 작으면서, 번호도 작은 사람 순으로 정렬 
print(kevin[0][0])