[백준] 1389 문제 in 파이썬

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

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

문제

풀이

Key

• 문제를 해결하기 위한 키는 너비 우선 탐색과 플로이드-워셜 알고리즘을 활용하는 것이다.
• 플로이도-워셜의 경우 모든 노드 간 최단 경로 계산에 사용되는 알고리즘이라 위 문제에 사용해도 적합할 것 같다는 생각이 들었지만, 시간복잡도가 O(n^3)이기에 너비 우선 탐색을 사용해 보고자 했다.

예전에 작성했던 코드 변형 시도

• ‘BFS와 DFS’라는 백준 문제를 풀었을 때 사용했었던 BFS 코드를 변형하는 식으로 문제를 풀었다.
  
• 이 함수는 그래프와 시작노드를 입력 받아 맨 끝의 노드까지 방문한 노드를 순서대로 vstd라는 배열에 저장하여 vstd 배열을 반환한다.
• 그러나, 케빈베이컨 문제를 풀기 위해서는 모든 노드 간 최단 경로를 탐색해야 하므로 입력으로 들어갈 변수를 (그래프, 시작노드) 에서 (그래프, 시작노드, 도착노드)까지 바꾸며 코드를 수정하기 시작했다.

기본 로직

그래프 생성

• 그래프를 저장한다. 이때 딕셔너리를 그래프의 자료형으로 활용하고 노드, 연결된 노드를 key, value 값으로 받는다.
• key 값과 value 값은 서로 저장하여 양방향 노드가 되도록 그래프를 구성한다.
  

  BFS

• 시작 노드 s와 케빈 베이컨 단계 수를 큐에 넣는다.
• 현재 노드 u에 큐 안에서 가장 왼쪽 노드 값을 할당, steps에 단계 수를 할당한다.
• 현재 노드 u가 도착 노드 t가 될 때까지 vstd 배열에 u를 추가한다.
• t에 도달하면 steps를 반환한다.
  

  최소 단계 수

• 각 노드별 steps를 비교하여 가장 작은 단계수를 출력한다.

완성된 코드