케빈 베이컨의 6단계 법칙

문제분석

제목과 문제가 길어서 위압감이 들긴 하지만, 편안한 BFS문제이다.

  • 1부터 N까지의 사람들 간에 관계가 주어진다.
  • 각각의 사람들에 대해서 다른 사람들 까지의 최단거리를 구하고, 최단거리들의 합을 저장한다. 이때, 번호가 가장 작은 ‘사람’을 출력해야 함으로 몇 번인지도 추가로 저장한다.
  • N까지 모두 탐색을 한 후, 최단거리가 저장되어있는 배열을 정렬해 가장 작은 수를 가진 사람을 출력한다.

Plus

  • 친구들 간의 관계를 저장할 때, dictionary를 사용했다. 리스트에 정보를 저장하는 것이 시간복잡도가 더 크다. 이 문제에서는 유저의 수가 최대 100이고, 관계의 수도 최대 5000이라서 리스트에 저장해도 시간초과가 발생하지 않는 것 같다.

  • 문제에서 케빈 베이컨의 수가 가장 작은 사람이 여러명일 경우 번호가 가장 작은 사람을 출력하라고 했음으로, 리스트를 정렬할 때 변수 두개를 활용해 정렬해준다.

res.sort(key = lambda x: (x[0],x[1]))

CODE

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

n,m=map(int,read().split())
# 친구간의 연결 리스트를 dictionary에 저장
#(이 문제에서는 입력의 크기가 최대 5000개로 많지 않기 때문에 상관없지만,
# 입력이 많아지면 dictionary로 받는것이 유리하다!)
friend=dict()
for _ in range(m):
    a,b=map(int,read().split())
    if a in friend:
       if b not in friend[a]: friend[a].append(b)
    else: friend[a]=[b]
    if b in friend:
       if a not in friend[b]: friend[b].append(a)
    else: friend[b]=[a]
#유저의 케빈 베이컨 수와 유저의 번호 저장
res=[]
for i in range(1,n+1):
    dp=list(2147000000 for _ in range(n+1))
    dp[i]=0
    dp[0]=0
    point=deque([i])
    while point:
        a=point.popleft()
        for x in friend[a]:
            if dp[x]>dp[a]+1:
                dp[x]=dp[a]+1
                point.append(x)
    res.append([sum(dp),i])
#케빈 베이컨 수를 기준으로 오름차순 정렬하고,
#케빈 베이컨 수가 같다면 유저 번호를 오름차순으로 정렬한다.
res.sort(key = lambda x: (x[0],x[1]))
print(res[0][1])


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]