1389번 케빈 베이컨 6단계 법칙

문제 설명

1389번: 케빈 베이컨의 6단계 법칙

 

나의 풀이

from collections import deque, defaultdict

# 기준이 되는 start_num을 기준으로 너비 탐색을 통해 kavin_bacon리스트의 인덱스 정보를 
# 나를 기준으로 얼마나 떨어져있는지 카운트 정보를 담는다.
# 현재 숫자가 tartget_num이라면, kavin_bacon의 해당 값을 반환
def bfs(graph, start_num, target_num):
    q = deque()
    q.append(start_num)
    kavin_bacon = [0] * (len(graph) + 1)

    while q:
        cur_num = q.popleft()

        if cur_num == target_num:
            return kavin_bacon[cur_num]

        for adj_num in graph[cur_num]:
            if not kavin_bacon[adj_num]:
                kavin_bacon[adj_num] = kavin_bacon[cur_num] + 1
                q.append(adj_num)

# 관계 정보가 담긴 그래프 생성
# 나: [나와 연결된 번호들이 담긴 리스트]
graph = defaultdict(list)
n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 1~n번까지 모든 번호들과의 케빈 카운트를 더해서 최소가 되는 것을 구함.    
answer = []
for i in range(1, n+1):
    kavin_cnt = 0
    for j in range(1, n+1):
        kavin_cnt += bfs(graph, i, j)

    answer.append(kavin_cnt)
print(answer.index(min(answer)) + 1)

bfs 함수 -> start_num, target_num이 몇단계로 연결이 되어있는지 확인하는 함수 

 - 번호를 인덱스로 하여금 관계가 몇번째인지 업데이트를 하여 targetNum이 나오면 해당 인덱스를 반환

 

결국엔 각 번호마다 모두 확인해서 최소가 되는 값의 번호를 반환하는 것.