[Baekjoon/Python] 1389번: 케빈 베이컨의 6단계 법칙 - 효과는 굉장했다!

[Baekjoon/Python] 1389번: 케빈 베이컨의 6단계 법칙 - 효과는 굉장했다!

반응형

알고리즘 분류

그래프 이론

그래프 탐색

너비 우선 탐색

플로이드-와샬

SOLUTION

import sys from collections import deque def bfs(realationship, start_node): num = [0] * (N+1) # 각각 노드가 몇번의 케빈 베이컨 수인지 측정을 위해 구현 queue = deque([start_node]) # deque를 이용해 시간복잡도 줄임, q.pop(0)로 하면 구현은 되지만 시간이 길어짐 visited[start_node] = 1 # 방문처리 while queue: node = queue.popleft() for i in realationship[node]: if not visited[i]: # 방문하지 않은 노드일 때 num[i] = num[node] + 1 # i번 노드를 방문하기 위해 몇번 거쳤는지 추가 --> 가장 중요한 코드 , num[a] 는 이미 방문한 노드 이므로 + 1 queue.append(i) visited[i] = 1 # 방문처리 return sum(num) # 총 몇번 방문해서 케빈 베이컨을 만족했는지 return N, M = map(int, sys.stdin.readline().split()) realationship = [[] for i in range(N+1)] # 노드끼리 연결되어 있다는걸 보여줄 배열 생성 for _ in range(M): A, B = map(int, sys.stdin.readline().split()) realationship[A].append(B) realationship[B].append(A) result = [] for i in range(1, N+1): visited = [0 for _ in range(N+1)] result.append(bfs(realationship, i)) # 방문 수가 같을 때, 번호가 가장 작은 사람을 출력하기 위해 하나씩 순서대로 넣어줌 print(result.index(min(result))+1) # index는 0번째 부터 시작이므로 +1 해서 출력

from http://thflgg133.tistory.com/136 by ccl(A) rewrite - 2021-12-25 15:26:55