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

📌문제 출처

솔브닷 3++ 클래스 단계
https://www.acmicpc.net/problem/1389

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

❓ 문제

 

📗 풀이 코드

from collections import defaultdict, deque
input = open(0).readline

def bacon(x) : # x에서 출발해서 각 노드에 도착하는 최단 경로 bfs
    tmp_dic = {i:-1 for i in range(1,n+1)} # 노드 방문 여부(-1이면 미방문)
    stack = deque([[x,0]]) # x 노드 방문, 방문까지 이동 경로(최초는 0)
    while stack :
        node,mov_cnt = stack.pop()
        if tmp_dic[node] == -1 or tmp_dic[node] > mov_cnt : # 최초 방문이거나 더 짧은 경로를 찾았다면
            tmp_dic[node] = mov_cnt # 방문 횟수 갱신
            for new_node in dic[node] : # 간선으로 이어지는 새로운 노드들
                stack.append([new_node,mov_cnt+1]) # 새로운 노드와 방문까지 이동 경로
    # 모든 노드 확인 완료 시
    return(sum(tmp_dic.values()))

def solution(n,tree): # 각 노드별 최단 경로 bfs를 완성해서 최단경로의 합의 최소를 찾는 함수
    global dic # dic이란 함수를 solution 함수 안에서 생성했지만 bacon 함수 내에서도 사용할 것이므로
    dic = defaultdict(list) # defaultdict로 선언이 되지않은 key값을 불렀을때 default 값을 자동으로 선언
    for a,b in tree: # 각 노드별 이어지는 간선 배열의 집합
        dic[a].append(b)
        dic[b].append(a)
    num_bacon = float('inf') # 최소 베이컨 수
    bacon_node = 0 # 최소 베이컨 수가 나오는 최단 경로
    for i in range(1,n+1):
        tmp_bacon = bacon(i)
        if num_bacon > tmp_bacon : # 베이컨 수가 작은 사람을 찾았다면
            num_bacon,bacon_node = tmp_bacon,i
    return bacon_node

if __name__ == '__main__':
    n,m = map(int,input().split())
    tree = [list(map(int,input().split())) for _ in range(m)]
    print(solution(n,tree))