[python]1389번 케빈 베이컨 6단계 법칙,BFS와 플로이드 알고리즘

내간 푼 방식은 BFS였다.

아직 플로이드에 대한 숙련도가 부족해서인지 떠올리지도 못했다

BFS로 떠올릴 수 있었던 것은 양방향 그래프성질에서

가장 최소값들의 합인 번호를 찾아야했기에, 

최소 이동으로 값을 구할려다 보니 자연스럽게 BFS가 떠올랐다.

 

from collections import deque
import sys
input = sys.stdin.readline
nodes,edges = map(int,input().split())
graph = [[]for i in range(nodes+1)] #그래프에 양방향 그래프 저장
for i in range(edges):
    fst,scd = map(int,input().split())
    graph[fst].append(scd)
    graph[scd].append(fst)
rst = [1e9,0] #최솟값을 추려내기 위한 기준값 설정
for i in range(1,nodes+1):
    tmp = 0 #임시 저장 값
    for j in range(1,nodes+1):
        visit = [0 for i in range(nodes+1)] #중복값 방문 방지
        stg = deque() #BFS를 위해
        stg.append((i,j,0)) #시작값 설정
        visit[i] = 1
        while stg:
            cur = stg.popleft()
            if cur[0]==cur[1]: #목적지에 도달했을 때
                tmp +=cur[2] #이동거리 값 추가
                break 
            for next in graph[cur[0]]:
                if not visit[next]:
                    visit[next] = 1
                    stg.append((next,cur[1],cur[2]+1)) #다음 그래프로 이동
    if tmp<rst[0]: #합산한 임시 값이 기준보다 작을 시
        rst[0] = tmp #기준점 갱신
        rst[1] = i #갱신한 노드 저장
print(rst[1]) #노드 출력

 

찾아보니 플로이드로 푼 사람 풀이도 있었다

https://www.acmicpc.net/source/54648470

로그인

tjddn929님의 풀이

n, m =map(int, input().split())

arr = [[987654321 for j in range(n + 1)] for i in range(n + 1)]

for i in range(1, n + 1):
    arr[i][i] = 0
for i in range(m):
    u ,v = map(int, input().split())
    arr[u][v] = 1
    arr[v][u] = 1

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]) #플로이드 개념

total = 987654321
idx = -1
for i in range(1, n + 1):
    #print(sum(arr[i][1:])) 
    if sum(arr[i][1:]) < total: #각 노드별로 모든 이동거리 합
        total = sum(arr[i][1:])
        idx = i
print(idx)