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

문제

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

 

문제 링크 : https://www.acmicpc.net/problem/1389

 

문제 풀이

목적 : 다른 사람과의 관계 거리 수를 구하여, 모든 사람이 다른 사람들과의 관계 수의 총합 중 가장 적은 수를 가진 최소 인덱스를 구하는 것

이 문제는 모든 사람이 적어도 한 명의 친구가 있다는 가정 하에, 다른 사람과 몇 번째 순서로 관계를 갖는지 찾는 것이다.  모든 사람과 다른 모든 사람간의 최소(거리를 가진)관계를 확인하기 위해, 각 사람이 1의 가중치로 친구와 연결된 노드라고 가정했을 때 플로이드-워셜 알고리즘으로 문제를 해결할 수 있다. 

플로이드 워셜 알고리즘은 매 반복문에서 중간 노드를 선택하고, 이후 모든 노드에 대해 해당 중간 노드를 거쳐 더 짧은 길이를 선택하는 과정을 반복, 거리 테이블을 갱신하는 방식으로 이루어진다. 

 

풀이 이후 다른 블로그를 보던 중, 최소 인덱스를 구할 때 반복문으로 인덱스를 갱신하는 방법보다, index 함수를 활용하여 훨씬 수월하게 풀이한 코드가 있어, 해당 코드를 추가하였다.

참고한 블로그 링크 : https://chaewsscode.tistory.com/98

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

 

 

코드

# https://www.acmicpc.net/problem/1389 케빈 베이컨 문제
# 플로이드 워셜 방법
import sys
input = sys.stdin.readline

n,m=map(int,input().split(' '))
INF = 10**9
board=[[INF for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
  i,j = map(int,input().split(' '))
  board[i][j]=1
  board[j][i]=1

for i in range(1,n+1):
  board[i][i]=0    

# 'k' 노드를 중간 노드로 할 경우의 거리를 탐색하기 때문에, 알고리즘의 정의에 따라 k-i-j 순서로 진행한다. i-j-k 와 같은 순서로 진행하면, [i,j]의 위치에 대해 다른 값들이 갱신되지 않은 상태로 지나갈 수 있기 때문에 플로이드-워셜 알고리즘의 정의에 맞는 갱신이 이루어지지 않을 수 있다.
for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      if i==j:
        continue
      value=min(board[i][j], board[i][k]+board[k][j])
      board[i][j]=value
      board[j][i]=value

# 답을 구하는 방법 1: 반복문으로 minv 갱신
answer=0
minv=INF
for i in range(1,n+1):
  val=sum(board[i][1:])
  if minv>val:
    answer=i
    minv=val

print(answer)

# 답을 구하는 방법 2: list 자료형의 index 함수를 사용하는 방법
# 블로그 참고 : https://chaewsscode.tistory.com/98
lst=[sum(board[i][1:]) for i in range(1,n+1)]
print(lst.index(min(lst))+1)