[Python] 백준 1389번 - 케빈 베이컨의 6단계 법칙(BFS) 문제풀이

문제링크

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

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

 

알고리즘

1. 이 문제를 보고 처음부터 BFS로 풀어야지~ 하고 생각하지 못한다면 나처럼 많이 헤맬 것이다. 재귀로 처음에 풀다가 recursion 에러가 왕창 나버렸다
2. 일반적인 BFS 함수를 만들어주고 deque로 구현하는 습관을 들이자. popleft()는 list의 pop()보다 실행속도가 훨씬 빠르다.

 

추가적으로, 이번에 공부한 플로이드-와샬 알고리즘을 사용해도 쉽게 구할 수 있다. 

Floyd - Warshall 알고리즘은 최단거리 알고리즘 중에서도 모든 출발점에서 모든 도착점까지의 최단거리를 구하는 알고리즘이라 이번 문제에 아주 적합하다.

 

코드 1 - BFS

from collections import defaultdict, deque
import sys


def bfs(graph, start):
    num = [0] * (n + 1)
    visited = [start]
    q = deque()
    q.append(start)

    while q:
        x = q.popleft()
        for i in graph[x]:
            if i not in visited:
                num[i] = num[x] + 1
                visited.append(i)
                q.append(i)
    return sum(num)


if __name__ == "__main__":
    input = sys.stdin.readline
    graph = defaultdict(list)

    n, m = map(int, input().split())
    for i in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    res = []
    for i in range(1, n + 1):
        res.append(bfs(graph, i))

    print(res.index(min(res)) + 1)

 

코드 2 - 플로이드-와샬 알고리즘

import sys

input = sys.stdin.readline

INF = 10**9

n, m = map(int, input().split())
graph = [[0] * n for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u - 1][v - 1] = 1
    graph[v - 1][u - 1] = 1

# 플로이드 와샬
for k in range(n):  # 경유 지점
    for i in range(n):  # 시작 지점
        for j in range(n):  # 도착 지점
            if i == j:
                continue
            elif graph[i][k] and graph[k][j]:
                if graph[i][j] == 0:
                    graph[i][j] = graph[i][k] + graph[k][j]
                else:
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

min_cost = INF
min_person = -1
for k in range(n):
    result = 0
    for i in range(n):
        result += graph[k][i]
    if min_cost > result:
        min_cost = result
        min_person = k

print(min_person + 1)

 

제출결과

종종 언어를 안바꾸고 내서 틀린다...

맨 밑의 결과가 BFS 코드이고 맨 위가 플로이드-와샬 알고리즘이다. 코드를 봐도 삼중 for문이 있는 플로이드와샬 알고리즘보다는 bfs가 압도적 효율적일 것을 알 수 있다.