[백준 1389번] 케빈 베이컨의 6단계 법칙 (Python/파이썬)

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

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

본인은 BFS를 이용해서 문제를 풀었다.

친구 관계 리스트를 만들어주고, 친구를 한번 건너 뛸때마다 (이전 친구 단계+1, 현재친구)를 튜플로 큐에 저장하였다.

BFS탐색이 모두 끝나고는 처음 시작한 친구의 케빈 베이컨의 수를 구해서 리턴해주었다.나온 케빈 베이컨의 수 중에서 가장 작은 친구를 출력해야하므로 마지막에 정렬까지 해주었다..

당연하지만 방문 리스트도 만들어서 한번 방문한 곳은 True로 바꿔 재방문하지 않게 하였다.

코드는 다음과 같다..

 

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int,input().split())
friends = [[] for _ in range(N+1)]

## 친구 리스트 생성
for _ in range(M):
  a, b = map(int,input().split())
  friends[a].append(b)
  friends[b].append(a)

## 몇번째 만에 친구와 만나는지 BFS탐색하고 케빈 베이컨의 수까지 구하기
def BFS(step,e):
  queue = deque([])
  queue.append((step,e))
  while queue:
    (tmp_step,tmp) = queue.popleft()
    for i in friends[tmp]:
      if not visited[i]:
        visited[i] = True
        queue.append((tmp_step+1,i))
        KB_num[i].append(tmp_step+1)
  KB = 0
  for i in range(1, N+1):
    try:
      KB += KB_num[i][0]
    except:
      pass
  return KB

## 각각의 친구마다 BFS돌리기
total = []
for i in range(1,N+1):
  visited = [False for _ in range(N+1)]
  KB_num = [[] for _ in range(N+1)]
  visited[i] = True
  total.append((BFS(0,i),i))
  
## 구한 케빈 베이컨의 수중에서 가장 작은것 찾기
total.sort()
print(total[0][1])

 

 

 

 

 

 

평범한 BFS문제인거같다.

 

 

글이나 코드에 대한 조언 모두 환영합니다.