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

[문제]

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

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

 

[풀이]

 

main 함수

graph = [[] for _ in range(n+1)]
# print(graph) -> [[], [], [], [], [], []]

양방향 노드로 그래프를 만들어준다. 여기서 범위가 n+1인 이유는 노드의 번호가 0이 아닌 1부터 시작하기 때문이다.

 

    for i in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

각 인덱스마다 몇 번 노드와 연결되어 있는지를 저장한다.

예제를 입력창에 넣을 경우, print(graph) 를 하게 되면 [[], [3, 4], [3], [1, 4, 2], [1, 5, 3], [4]] 가 출력된다.

---

BFS 함수

 

BFS 코드는 deque함수를 이용해서 만들어주었다. list.pop(0) 사용 시 시간복잡도가 O(N)으로 매우 비효율적인 코드가 만들어지기 때문에 deque 함수로 popleft() 를 사용한다.

 

 

BFS 함수의 작동 순서를 보면 위의 풀이와 같다. 우선 메인 함수의

    for i in range(1, n+1):
        result.append(bfs(graph, i))

위 코드에서 노드 1번부터 BFS 함수를 호출하기 때문에 start 로 1이 주어졌을 때의 풀이이다. 

 

 

BFS 함수 실행시 start 노드에서 다른 노드로 갈 수 있을 때, num 리스트의 각 인덱스에 맞는 값을 1씩 더해주어 다음 BFS함수로 그 값을 넘겨주고 retrun으로 num 리스트에 있는 수들의 총합을 받아온다.

 

마지막으로 result 리스트를 만들어 노드 1번부터 n번까지 결과 값 sum(num) 값을 result 리스트에 넣어준다. 마지막으로 result.index(min(result))+1 를 통해 가장 작은 숫자가 있는 인덱스를 구해준다.

 

 

[코드]

import sys
from collections import deque


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

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


if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

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

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