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

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

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

 

# 조건

• 모든 사람들은 최대 6단계 이내로 서로 아는 사람으로 연결
• 케빈 베이컨 게임은 임의의 두사람이 최소 몇 단계 만에 이어질 수 있는지 계산
• 유저의 수 N(0<=N<=100), 친구 관계의 수 M (1<=M<=5000)
• BOJ의 유저 중 케빈 베이컨의 수가 가장 작은 사람을 출력

 

# 접근 방법 및 Solution

• 그래프 탐색 중 bfs 이용해준다.
• 시작지점부터 각 노드까지의 방문 기록을 +1 씩해주며 거리 계산해준다.
• 모든 번호가 1로 시작하고, 케빈 베이컨의 번호를 출력하기 때문에 따로 -1 해주지 않아도 된다.

 

import sys  
from collections import deque  
sys.stdin = open('input.txt')  
  
def bfs(s):  
    q = deque()  
    q.append(s)  
    visited[s] = 1  
    while q:  
        start = q.popleft()  
        for i in range(N+1):  
            if relation[start][i] and visited[i] == 0:  
                visited[i] = visited[start] + 1  
                q.append(i)  
  
  
  
  
# 사람 번호, 관계의 수  
N, M = map(int, input().split())  
  
# 사람 관계 기록 리스트  
relation = [[0]*(N+1) for _ in range(N+1)]  
for k in range(M):  
    a, b = map(int, input().split())  
    relation[a][b] = 1  
    relation[b][a] = 1  
  
min_value = 10000000  
idx = 0  
for i in range(1, N+1):  
    # 방문기록과 각 노드까지의 거리 체크 변수  
    visited = [0] * (N + 1)  
    bfs(i)  
    # 최소 값 갱신 및 인덱스 기록  
    if min_value > sum(visited):  
        min_value = sum(visited)  
        idx = i  
  
print(idx)