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

문제

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

풀이

• 케빈 베이컨 합의 최소값

케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.
즉, 최단 거리를 계산하는 문제이므로 BFS를 이용하여 문제를 풀면 된다.

이 문제에선 친구 관계가 주어지기 때문에 graph를 인접 행렬이 아닌 인접 리스트로 구현하였습니다.

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

왜 인접 리스트로 접근했나?

연결된 노드만 저장하여 빠름
특정 노드의 친구를 탐색할 때 O(degree), 즉 연결된 친구 수만큼만 반복하면 됩니다.

평소 bfs 문제를 풀 때는 vistied를 메인문에 선언했지만, 이 문제는 1번부터 n번 사람까지 모두 합을 구해야 하므로 함수 내에 선언했습니다.

def bfs(v):
    queue = deque([v]) # 시작값 추가
    visited = [-1] * (n+1) # 방문 여부 + 거리 저장(-1: 미방문)
    visited[v] = 0 # 자기 자신은 거리 0

    while queue:
        node = queue.popleft()
        for i in graph[node]: # 현재 노드의 친구 확인
            if visited[i] == -1: # 방문 안 했으면
                queue.append(i)
                visited[i] = visited[node] + 1 # 거리 +1
    
    return sum(visited[1:]) # 1번부터 n번까지 거리 총합

이제 입력받은 값을 이용해 1번부터 n번까지 bfs를 모두 돌려봅니다.

val = 1e9 # 최소값 초기화
res = 0 # 가장 작은 사람 번호

for i in range(1,n+1):
    num = bfs(i)
    if num < val: # bfs(i)값이 최소값 보다 작으면
        val = num # 최소값 갱신
        res = i # 가장 작은 사람 번호 저장
    
print(res)

코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(v):
    queue = deque([v])
    visited = [-1] * (n+1) 
    visited[v] = 0

    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if visited[i] == -1:
                queue.append(i)
                visited[i] = visited[node] + 1
    
    return sum(visited[1:])

if __name__ == "__main__":
    n,m = map(int,input().split())
    
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)

    val = 1e9
    res = 0

    for i in range(1,n+1):
        num = bfs(i)
        if num < val:
            val = num
            res = i
    
    print(res)