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

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

 

문제

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

케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이으로 이 게임을 했을 때 모든 사람 

나오는 단계의 총 합을 케빈 베이컨의 수라고 할 때 이때 이 수가 가장 적은 사람을 찾는 문제이다.

 

이때 단계를 계산하는 방법으로 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해 보자.

1은 2까지 3을 통해 2단계 만에 연결될 수 있으며, 3까지는 1단계 , 4까지 1단계 , 5까지는 4를 통해 2단계만에 연결된다

그러면 케빈 베이컨의 수는 2+1+1+2 = 6이다.

그럼 1을 했으니 2도 하고 3도 하고 5까지 모두 다 했을 때 케빈 베이컨의 수가 가장 작은 사람을 출력하면 된다.

입력

첫 줄에는 유저수 N 과 친구 관계의 수 M이 주어진다.

둘 때 줄부터 M 개의 줄에 친구 관계가 주어진다.

이때 친구관계는 A와 B로 이루져 있으면 A와 B가 친구이면 B와 A도 친구이다.

출력

첫째줄에 케빈 베이컨의 수가 가장 작은 사람을 출력한다 만약 여러 명일 경우 가장 번호가 작은 사람을 출력한다.

풀이

이문제를 보면 결국 현재 시작 번호로부터 모든 사람을 한 번씩 연결하여 만나야 한다. 

그러면 사용할 수 있는 방법이 DFS와 BFS가 있다. 

DFS인 경우는 깊이 우선 탐색으로 모든 사람과 만날 수는 있지만 그 사람이 몇 단계인지 알기 어렵다.

그러면 BFS를 사용하면 가까이 있는 노드부터 탐색하기에 이걸 이용하여 그 사람과 몇 단계에 만나는 체크할 수 있다.

그렇기에 기존 BFS 코드에서 몇 단계인지 체크하기 위한 리스트를 추가로 만들어 그 값을 0으로 하고 사람수만큼 크기를 만든다.

def bfs(g,vis,count,s):
    q=deque([s])
    vis[s]=True

    while q:
        v=q.popleft()
        for i in g[v]:
            if not vis[i]:
                count[i]=count[v]+1
                q.append(i)
                vis[i]=True

count라는 게 현재 몇 단계인지 체크하기 위한 리스트이다.

count를 찾고자 하는 사람의 위의 사람의 단계에서 +1을 하여 현재 찾은 사람이 몇 단계인지 알 수 있다.

그 이유는 위에서 말했듯이 BFS 알고리즘 특성상 가까이 있는 노드부터 먼전 탐색하기 때문이다 

만약 1과 1단계로 연결된 사람이 3, 4 이면 3,4부터 탐색하기에 count [3], count [4]의 값은 1이 될 수 있고

그다음 3에서 연결된 사람이 2 이면 count [2]=count [3]+1로 2번 사람이 몇 단계인지 구할 수 있다.

코드

 

from collections import deque

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]


def bfs(g,vis,count,s):
    q=deque([s])
    vis[s]=True

    while q:
        v=q.popleft()
        for i in g[v]:
            if not vis[i]:
                count[i]=count[v]+1
                q.append(i)
                vis[i]=True
        

ans=[]

for i in range(m):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for i in range(n):
    vis=[False for _ in range(n+1)]
    count=[0 for _ in range(n+1)]
    bfs(g,vis,count,i+1)
    ans.append(sum(count))

minNum=min(ans)
print(ans.index(minNum)+1)