BOJ - 1389

백준 문제 링크
케빈 베이컨의 6단계 법칙

❓접근법

1. BFS를 사용했다.
2. bfs함수 안에서 리스트 변수인 count를 만들어 주고,
   자식 노드(i)를 처음 방문한다면,
   부모 노드(x)의 count값 + 1을 자식노드의 count값에 넣어준다.
   count[i] = count[x] + 1
3. queue가 비었을 때, count에 들어간 합계를 반환한다.
4. 1~N까지 for문으로 answer[i]에 bfs(i)를 넣어준다.
5. 케빈 베이컨의 수가 가장 작은 인덱스를 반환하면 끝

👌🏻코드

from collections import deque
N,M = map(int, input().split())

lst = [[] for _ in range(N+1)]

for _ in range(M):
    x,y = map(int, input().split())
    lst[x].append(y)
    lst[y].append(x)   

answer = [0] * (N+1)

def bfs(v):
    queue = deque()
    queue.append(v)
    
    count = [0] * (N+1)
    visited[v] = True
    
    while queue:
        x = queue.popleft()
        
        
        for i in lst[x]:
            if not visited[i]:
                count[i] = count[x] + 1
                visited[i] = True
                queue.append(i)
                
    return sum(count)


            
for i in range(1, N+1):
    visited = [False] * (N+1)
    answer[i] = bfs(i)
    
print(answer.index(min(answer[1:])))