BOJ1389 케빈 베이컨의 6단계 법칙

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

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

 

난이도: 실버1

소요시간: 35분

 

문제를 보자마자 다익스트라를 써야하나 라는 생각이 들었다. 그러나 오늘 풀 주제는 bfs였기에 bfs로 풀었다. 

풀고나니 최단거리문제이면서 모든 거리가 1이라면 bfs를 써도된다는 것을 깨달았다. 앞으로 전형적인 최단거리 문제라도 거리가 1이라면 bfs도 고려를 해보아야겠다. 내일은 최단거리로도 한번 풀어보아야겠다.

 

#16:07 실버1 35분
import sys
from collections import deque

N,M = map(int,sys.stdin.readline().split())
graph=[[] for _ in range(N+1)]
visited = [False]*(N+1)

for i in range(M):
    temp1,temp2= map(int,sys.stdin.readline().split())
    if temp2 not in graph[temp1]:
        graph[temp1].append(temp2)
    if temp1 not in graph[temp2]:
        graph[temp2].append(temp1)


def bfs(start):
    visited = [False] * (N + 1)
    deq= deque([[start,0]])
    bacon=0
    while(deq):
        temp=deq.popleft()
        q=temp[0]
        depth=temp[1]
        if visited[q] == True:
            continue
        bacon += depth
        depth+=1
        visited[q]=True
        for g in graph[q]:
            deq.append([g,depth])
    return bacon

result=[]

for i in range(1,N+1):
    result.append([bfs(i),i])

result.sort(key= lambda x:(x[0],x[1]))

print(result[0][1])