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

http://acmicpc.net/problem/1389

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

<접근>

문제에서 구하고자 하는 '케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램'은 즉 '모든 최단경로들의 합'이다. 따라서 모든점에서 다익스트라 알고리즘을 구해서 모든 경로의 합을 더하여 제일 짧은 사람을 구하면 된다. 

• 다익스트라 알고리즘으로 한 점에서 갈 수 있는 모든 노드 최단거리를 구하여 모두 더한다.
• 존재하는 모든 노드들의 구한 합을 비교하여 제일 짧은 노드를 출력한다.
• 최단 거리가 같은 노드가 존재하는 경우 번호가 작은 사람을 구하면 되므로 N명이면 1번부터 비교하는 것이 아닌 N부터 비교한다.

해당 풀이는 다익스트라 알고리즘을 선행해야 하므로 아래 게시을을 보고오는 것을 추천한다.

 

2021.03.18 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

[보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

<입력>

N, M = map(int, input().split())

graph = {i+1: [] for i in range(N)}

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

    if b not in graph[a]:
        graph[a].append(b)
    if a not in graph[b]:
        graph[b].append(a)

 

사람의 수 N과 관계선의 수 M을 입력받는다.

 

그래프에 N명의 key를 미리 설정한다. value는 리스트로 받는다.

 

관계선의 수 M만큼 반복해준다. a와 b의 쌍방 관계이므로 a키와 b키에 서로의 값을 추가해준다.

<함수 1>

import heapq


def dijkstra(graph, start_node):
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0

    queue = [[distances[start_node], start_node]]

 

알고리즘의 시간을 단축시키기 위해 heapq를 사용한다.

 

출발 지점으로 부터 거리를 담을 distances의 값을 줄어들수록 갱신할 것이다. 따라서 초기 값을 최대수인 float('inf')로 설정을 한다.

출발지점의 값은 자기자신이므로 0으로 설정한다.

 

queue에 [현재거리, 현재 노드]를 넣는다. 처음이므로 [0, 출발 노드]를 넣는다.

<함수 2>

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        for new_node in graph[current_node]:
            new_distance = current_distance+1
            if new_distance < distances[new_node]:
                distances[new_node] = new_distance
                heapq.heappush(queue, [new_distance, new_node])

    return distances

 

queue에서 현재노드와 현재 노드까지의 거리를 받아온다.

 

현재 노드에서 갈 수 있는 다음 노드를 graph에서 하나씩 받아온다.

다음 노드까지의 새 거리(new_distance)는 1을 더한 값이므로 현재거리(current_distance)에서 1을 더해준다.

만약 이 새 거리(new_distance)가 distances에 담겨있는 값보다 작으면 해당 값으로 갱신해준다. 그리고 queue에 해당 값을 넣어주고 위의 작업을 반복한다.

<출력>

shortest_distance = float('inf')
answer = 0

for i in range(N):
    distances = dijkstra(graph, N-i)

    distance_sum = 0
    for j in distances:
        distance_sum += distances[j]

    if shortest_distance >= distance_sum:
        shortest_distance = distance_sum
        answer = N-i

print(answer)

 

한 노드에서 모든 노드까지의 합을 구해야 한다. 그래서 해당 값이 제일 작은 노드를 출력하고, 만약 같은 값이 있다면 작은 수를 출력해야 한다. 따라서 작은 합을 구하기 위해 처음 값을 가장 큰 float('inf')로 설정한다.

 

작은 수를 구하기 위해서 N번째 수부터 작아지는 순서로 비교한다. dijkstra함수를 통하여 최단 거리를 구하고, 모든 값을 더해서 distance_sum에 넣어준다. 만약 shortest_distance와 비교하여 더 작거나 같다면(같은 이유는 값이 같을 때 더 작은 값으로 갱신하기 위해) shortest_distance의 값을 갱신하고 answer의 값을 해당 노드의 번호로 바꾼다.

 

<전체 코드>

import heapq


def dijkstra(graph, start_node):
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0

    queue = [[distances[start_node], start_node]]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        for new_node in graph[current_node]:
            new_distance = current_distance+1
            if new_distance < distances[new_node]:
                distances[new_node] = new_distance
                heapq.heappush(queue, [new_distance, new_node])

    return distances


N, M = map(int, input().split())

graph = {i+1: [] for i in range(N)}

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

    if b not in graph[a]:
        graph[a].append(b)
    if a not in graph[b]:
        graph[b].append(a)


shortest_distance = float('inf')
answer = 0

for i in range(N):
    distances = dijkstra(graph, N-i)

    distance_sum = 0
    for j in distances:
        distance_sum += distances[j]

    if shortest_distance >= distance_sum:
        shortest_distance = distance_sum
        answer = N-i

print(answer)