[백준-실버1] 1389번 케빈 베이컨의 6단계 법칙(BFS, 파이썬)

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

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

 

<내 코드>

- 알고리즘 분류를 보니 BFS 또는 플로이드-와샬을 이용하는 문제이다. 플로이드 와샬이 뭔지 몰라서,, 공부해야겠다.

- 나는 BFS를 이용해서 풀었다.

- 문제에서 설명하는 케빈 베이컨 수는 해당 노드에서 다른 노드까지 몇단계만에 이동할 수있는지를 점수로 환산한다.

- 따라서 나는 BFS를 이용해서 해당 노드별로 거리를 파악했다.

- BFS함수를 호출할때마다 dist리스트를 초기화하고, 입력 받은 노드와 다른 노드들의 거리를 파악했다.

  (문제에서 모든 노드들은 전체적으로 연결되어있음)

- BFS함수의 리턴으로 dist리스트의 합을 리턴한다. (이때 dist의 합이 케빈 베이컨 수가 된다.)

- 메인 부분에서 반복문을 돌면서 1-N까지 순회하고, 이때 각 노드별로 거리를 파악하기 위해 visited를 초기화해주고

  result[i]에 bfs(i)를 덮어 씌운다.

- 최종적으로 result 에서 가장 작은 값을 찾는데 이 때 0번 인덱스는 사용하지 않으므로 0번은 제외하고 찾는다.

- 결과는 min_val의 인덱스를 출력한다.

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
    
def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v] = True
    dist = [0]*(n+1)
    while queue:
        pop = queue.popleft() 
        for i in graph[pop]:
            if visited[i] == False:
                visited[i] = True
                dist[i]  += dist[pop]+1
                queue.append(i)
    return sum(dist)
        
result = [0]*(n+1)
for i in range(1,n+1):
    visited= [False]*(n+1)
    result[i] = bfs(i)

min_val = min(result[1:])
print(result.index(min_val))