[baekjoon] 백준 1389번 : 케빈 베이컨의 6단계 법칙 (by python 파이썬) bfs

https://www.acmicpc.net/problem/1389

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

 

정답 code

# 케빈 베이컨의 6단계 법칙
from collections import deque
def bfs(num, n):
    bacon = [0]*(n+1) #케빈베이컨수 계산
    visited = [num] #방문 숫자 기억
    queue = deque()
    queue.append(num)
    while queue:
        k = queue.popleft()
        for i in cabin[k]:
            if i not in visited:
                visited.append(i)
                queue.append(i)
                bacon[i] = bacon[k] + 1 #해당유저에서 한단계 더 나아감으로 1추가
    return sum(bacon)




n, m = map(int,input().split())
cabin = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    cabin[a].append(b)
    cabin[b].append(a)

result = [] #케빈 베이컨수합 저장

for num in range(1, n+1):
    result.append(bfs(num,n))

print(result.index(min(result))+1)  #정답 index에 1추가한 값 출력

 

이번 문제는 bfs를 활용하여 풀 수 있는 문제다

 

solution

예제를 풀어보면 아래와 같다

[[] [3,4] [3], [1,2,4], [1,3,5], [4]]

이를 1번 인덱스 부터 n+1까지 bfs탐색을 해준다.

 

그래서 1부터 n 까지의 케빈베이컨수를 result에 저장해 최소 값을 출력하면된다.

 

단순히 bfs문제에서 케빈베이컨수를 추가해 계산하면되는데 이걸 추가하는 과정에서 애를 좀 먹었다.

bfs함수에서 현재 탐색하고있는 수에서 다음단계로 너비탐색을 하면서 한단계 올라가기때문에 1을 추가해 케빈베이컨수를 계산하면된다.