[백준-1389] 케빈 베이컨의 6단계 법칙

문제

링크

코드

# DFS 사용
from collections import deque
n, m = map(int, input().split())

answer = [0] * (n+1)

friend = [[] for _ in range(n+1)]

for _ in range(m) :
    a,b = map(int, input().split())
    friend[a].append(b)
    friend[b].append(a)

# 1부터 n까지 
for i in range(1, n+1) :
    visited = [0] * (n+1)
    queue = deque()
    queue.append(i)
    while queue :
        q = queue.popleft()
        for f in friend[q] :
        # 방문하지 않고, 시작점(i)이 아닐 경우에만
            if visited[f] == 0 and f != i:
            	# 이전 사람의 값보다 +1
                visited[f] += visited[q] + 1
                queue.append(f)
    answer[i] = sum(visited)

# 1번을 기준
minVal = answer[1]
minPer = 1
for i in range(2, n+1) :
	# 2번부터 끝까지
    if minVal > answer[i] :
        minVal = answer[i]
        minPer = i
    elif minVal == answer[i] :
        minPer = min(minPer, i)

print(minPer)