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

1. 문제

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

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

2. 접근 방법

문제에 등장하는 케빈 베이컨 수는 해당 노드에서 다른 노드를 모두 방문하는 데 필요한 총 길이인데요,

결국 그래프의 최단 길이 문제라 다익스트라 혹은 플로이드 워셜로 풀이할 수 있습니다.

하지만 N이 500이하라서 플로이드워셜을 써도 되겠다 싶었습니다.

 

물론 bfs로도 풀이 가능합니다.

 

플로이드 워셜을 쓰기에 앞서 간단히 설명드리자면

 

거리를 담을 2차 배열을 graph로 초기화 합니다.

이 때 각각의 요소는 최대 거리인 100이상의 값이면 되므로 저는 1000으로 지정했습니다.

 

그리고 입력으로 들어오는 친구 관계를 1로 넣어줫습니다.

 

그리구 3중 for문을 사용하여 a와 b 사이 거리와 a에서 k를 들렸다가 k에서 b에 도착하는 것 중 더 짧은 것으로 갱신해줍니다.

 

요러케 하면 끄읏

 

3. 코드

python

N, M = map(int, input().split())
graph = [[1000] * (N+1) for _ in range(N+1)]

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

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

min_sum = 1e9
answer = 0

for i in range(len(graph)):
    if sum(graph[i]) < min_sum:
        min_sum = sum(graph[i])
        answer = i

print(answer)

4. 마치며

다익스트라보다 더욱 직관적인 플로이드 워셜입니다요