[백준/BOJ] - 1389번 python 풀이 - 케빈 베이컨의 6단계 법칙

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

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

---

어떻게 풀면 될까?

문제의 설명이 다소 복잡한 면이 있기 때문에 집중해서 읽어보면 친구의 친구의 친구의~~ 친구! 

"두 사람이 있다고 가정하고 그 둘이 몇 관계 만에 이어질 수 있는가"가 핵심인 문제이다.

 

일단 기본적으로 인원의 수와 인맥 관계에 대한 입력이 주어지는데, 이를 보자마자 든 생각은 

인맥 관계에 대한 설명이 나왔으니, 그래프에 해당 관계를 정리하면 되겠군.

 

결국 이 그래프는 탐색을 용도로 사용이 될 것임을 직감했다.

다만, dfs or bfs 둘 중 하나를 쓰면 될 거 같다는 생각이 들었는데,굳이 dfs를 활용해서 끝자락 까지 갔다올 필요 없이

bfs를 통해 넓게 진행해서 방문 처리가 안된 친구에게 방문처리 겸 몇 단계를 건너가야 만날 수 있는지의 지표를

남기기로 결정했다.

 

bfs를 통해 결과값들을 result에 저장하고 나서 min 값을 구하는 방법은 알겠으나,

• min값이 있는 idx 구하는 방법은?
• 겹치는 min 값의 소유자는 번호가 가장 작은 값을 구하시오!

 

해당 방법을 모두 만족할만한 방법을 찾는 중

arr.index(min(arr))

요 문법을 알게되었다.

min이라는 메서드는 기본적으로 idx가 낮은 값부터 비교하여 저장하기에 위의 2번 조건은 만족할 수 밖에 없다.

 

why? 

겹치는 값은 패스(부등호를 통해 비교 분석 진행)하기 때문에 idx가 갱신될 가능성이 없기 때문!

그렇기에 해당 값의 idx를 확인하는 index 메서드를 통해 결과 도출 가능!

 

---

from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
visited = [0]*(n+1)
arr = [[] for _ in range(n+1)]
result = []
maxi = sys.maxsize

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

def bfs(n):
    visited[n] = 1
    q = deque([n])
    while q:
        v = q.popleft()
        for item in arr[v]:
            if visited[item] == 0:
                visited[item] = visited[v] + 1
                q.append(item)


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