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

✏️ 문제

 

문제 파악

BFS 사용하는 문제 중 11725번 트리의 부모 찾기가 생각났던 문제..

인접리스트를 사용하면 쉽게 풀 수 있다!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 최단 경로
• 플로이드-워셜

 

 

코드

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
cnt = []

for _ in range(m):
  x, y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

def bfs(v):
  q = deque([v])
  visited[v] = 1
  
  while q:
    node = q.popleft()

    for neighbor in graph[node]:
      if visited[neighbor] == 0:
        visited[neighbor] = visited[node] + 1
        q.append(neighbor)

for i in range(1, n+1):
  visited = [0] * (n+1)
  bfs(i)
  cnt.append(sum(visited))

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

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS