[BOJ] 1389. 케빈 베이컨의 6단계 법칙

www.acmicpc.net/problem/1389

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

 

문제: 케빈 베이컨의 수가 최소인 사람의 번호를 출력하라.

 

문제 이해하기!!

케빈 베이컨이라하면

그래프의 한 노드에서 다른 노드로 최소 몇번을 걸쳐야 거기로 갈 수 있는지를 구하면 되는 문제입니다.

즉, BFS를 쓰면 되는 문제라고 볼 수 있습니다.

※ 다만, DFS를 쓰면 틀리니 주의하세요!

DFS를 쓰면 틀리는 이유는 깊이와 너비 우선 방식의 노드 접근법을 생각하시면 쉽게 알아차릴 수 있습니다.

 

제가 푼 방식을 설명하자면,

1. 주어진 입력을 딕셔너리로 저장합니다.

2. 전체 사람들을 한 명씩 골라, bfs로 관계를 파악하며 카운트를 셉니다.

3. 전체 사람들 중 케빈 베이컨 수가 제일 작은 사람의 번호를 출력합니다.

코드:

from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)
from collections import defaultdict, deque

def bfs(x, cnt):
    global res
    Q = deque(dic[x][:])
    visit[x] = True
    while Q:
        cnt += 1
        for _ in range(len(Q)):
            x = Q.popleft()
            if visit[x]:
                continue
            res += cnt
            visit[x] = True
            for i in dic[x]:
                Q.append(i)


N, M = map(int, input().split())
dic = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)

ans = []
for i in range(N, 0, -1):
    visit = [False] * (N + 1)
    res = 0
    bfs(i, 0)
    ans.append((res, i))

ans.sort()
print(ans[0][1])