알고리즘 - Python / 백준 - 1389번 : 케빈 베이컨의 6단계 법칙

1389번: 케빈 베이컨의 6단계 법칙 (acmicpc.net)

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

 

---

풀이

• 입력 노드가 1 ~ N 까지로 들어오고 , 모든 노드를 최단거리로 갈때 거치는 간선의 수의 합이 가장 작은 노드를 찾는 문제이다.
• BFS로 풀면 될 듯 싶어 , BFS로 노드를 탐색하고 해당 노드까지 가는데 걸린 간선수를 따로 리스트에 저장했다.
• 이후 그 노드에서 다른 노드로 간선을 하나 이동했다면 , 리스트에 저장한 이전 노드까지 움직이는데 거친 간선의 수 + 1 을 통해 거쳐가는 모든 노드들에 대해 거친 간선의 수를 리스트에 저장했다.
• 처음에 제출을 Python으로 하였는데 , 틀렸다고 나와 BFS 문제가 아닌가 싶었다. 혹시 몰라 PyPy3 으로 제출하니 맞았다고 나온다.
• 시간 복잡도 차이로 그런건 아닌 것 같은데 , 아무튼 맞았다고 하니 넘어가기로 했다.

 

import sys

n , m = map(int , sys.stdin.readline().split())

dic = {}

def bfs(dic, root,size):
  visited = []
  stack = [root]
  ans_stack = [0]*(size+1)

  while stack:
    n = stack.pop(0)
    if n not in visited:
      visited.append(n)
      if n in dic:
        sub_stack = list(set(dic[n]) - set(visited))
        for i in range(0,len(sub_stack)):
          stack.append(sub_stack[i])
          ans_stack[sub_stack[i]] = ans_stack[n] + 1
  ans = 0
  for i in range(0,len(ans_stack)):
    ans += ans_stack[i]
  return ans


for _ in range(m):
  nd1, nd2 = map(int , sys.stdin.readline().split())
  if nd1 not in dic:
    dic[nd1] = [nd2]
  else:
    dic[nd1].append(nd2)
  
  if nd2 not in dic:
    dic[nd2] = [nd1]
  else:
    dic[nd2].append(nd1)


min_k = bfs(dic ,1,n)
num = 1
for i in range(2,n+1):
  kevin = bfs(dic ,i,n)
  if min_k > kevin:
    min_k = kevin
    num = i
print(num)

---