[BOJ] 케빈 베이컨의 6단계 법칙

---

코드

import sys
import heapq
input = sys.stdin.readline

def dijkstra(start):
    dist[start-1][start-1] = 0        # 같은 노드간 거리는 0
    hq = []    # 최소힙
    heapq.heappush(hq, (start, 0))    # 최소비용 노드를 꺼낸다

    while hq:
        cur, d = heapq.heappop(hq)
        for adj in graph[cur]:
            # 인접 노드 간 거리는 항상 1
            # cur노드를 거쳐서 adj로 가는 비용이 현재 adj로 가는 최소비용보다 작으면 갱신
            if d + 1 < dist[start-1][adj-1]:
                dist[start-1][adj-1] = d + 1
                heapq.heappush(hq, (adj, d + 1))
                
# 입력
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
dist = [[10e5]*(n) for _ in range(n)]

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

# 모든 시작 노드로부터 다른 노드까지의 거리를 계산
for i in range(1, n+1):
    dijkstra(i)

minPersonNum = 0    # 구할 정답
minK = 10e5
for i in range(n):
    kv = sum(dist[i])
    if kv < minK:
        minK = kv
        minPersonNum = i+1
    elif kv == minK:
        if minPersonNum > i+1:
            minPersonNum = i+1
            
print(minPersonNum)

결과

풀이 방법

• 특정 노드 간 최단거리를 구해야 하므로 다익스트라 알고리즘을 사용하였다
• 최소힙을 사용한 다익스트라 알고리즘의 시간복잡도가 NlogN 이므로 문제에서 N이 최대 100이기 때문에 100 x 100log(100) = 20000 회 정도의 연산으로 충분히 해결할 수 있다고 판단하였다.

---