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

문제

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

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 반복문을 통해 모든 친구를 기준으로 탐색한다.

- 친구 관계를 확인하고 탐색하지 않은 친구라면 탐색한다.

- 탐색하면서 탐색하기까지 걸린 횟수를 체크한다.

- 케벤 베이컨의 수가 가장 작은 사람을 인덱스를 이용해서 출력한다.

코드

import sys
from collections import deque


# bfs 탐색
def bfs(v):
    queue = deque([v])
    visited[v] = 1

    while queue:
        target = queue.popleft()

        # 친구 관계를 확인하고 탐색하지 않은 친구라면 탐색한다.
        for i in graph[target]:
            if not visited[i]:
                # 탐색하기 위한 횟수를 체크한다.
                visited[i] = visited[target] + 1
                queue.append(i)


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

# 2차원 그래프를 표현
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# 케빈 베이컨의 수를 담는 리스트
res = []

# 반복문을 통해 모든 친구를 탐색한다.
for i in range(1, n + 1):
    visited = [0] * (n + 1)
    bfs(i)
    res.append(sum(visited))

# 가장 작은 케빈 베이컨의 수를 가지고 있는 사람의 인덱스 + 1 을 해주어 출력한다.
print(res.index(min(res)) + 1)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법