케빈 베이컨의 6단계 법칙

 

 

def BOJ1389() :
  n, m = map(int, input().split())
  temp = [[1e9] * n for _ in range(n)]
  for _ in range(m) :
    start, end = map(int, input().split())
    temp[start-1][end-1] = 1
    temp[end-1][start-1] = 1
  
  for mid in range(n) :
    for start in range(n) :
      for end in range(n) :
        if mid != end and temp[start][mid] and temp[mid][end]:
          temp[start][end] = min(temp[start][end], temp[start][mid] + temp[mid][end])
  
  result = 1e9
  p = 0
  for i in range(n) :
    total = sum(temp[i])
    if result > total :
      result = total
      p = i
  
  print(p+1)

BOJ1389()

 

접근방법 : 

1. 네트워크 관련 알고리즘 이다. => 플로이드 워셜, 벨만포드, 다익스트라

모든 경로에 대한 최단 거리의 접근이 필요하다 => 플로이드 워셜

2. 각 지점에서 시작했을때의 최단거리들로 업데이트 되었으므로 거리의 합을 계산해서 비교해주자

 

장애물 이였던 것 : 

1. 플로이드 워셜 알고리즘을 쉽게 떠올리지 못했고 적용하는 과정에서도 중간 지점의 위치를 잘못 설정하여서 애먹었다.

 

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

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