백준 1389

<케빈 베이컨의 6단계 법칙>

난이도 : 실버 1

1. 백준 문제
   1389

2. 코드 알고리즘

• 플로이드 워셜

11404의 풀이를 참고

플로이드-워셜 알고리즘은 다른 노드를 경유하는 게 중요할 경우 주로 사용 된다 (11404, 11403, 1389 문제의 공통점)

• 1389 풀이

경유하는 노드가 증가할 수록 단계 수가 증가하므로 인접리스트 값을 1로 설정

2-1. 슈도 코드

#1398

유저의 수 N 친구 관계의 수 M

D = (N+1)*(N+1) 행렬 만들기 (초기화는 max로)

for i in M:
	a, b 연결되있는 두친구 입력받기
	D[a][b] = 1 # 두친구가 1단계로 연결돼있음을 표시
	D[b][a] = 1 # 양방향 그래프임


for k in range():
	for s in range():
		for e in range()
			if 기존 경로보다 작으면 업데이트 하기

베이컨 리스트 크기 N+1 = 0 으로 초기화
for i in range(1부터 N+1까지)
	#베이컨[i]의 총합 찾기
	for j in range():
		if 자기 자신 제외
		else:
			베이컨[i] += D[i_자기자신][j_다른 노드] #단계수 더하기 (i에서 j까지 가는 베이컨 수 더하기)

베이컨[0] = max로 설정 #없는 값이므로 최소값으로 선정되면 안됨
min(베이컨)을 값으로 가지는 인덱스 출력(여러명일 경우 번호가 작은 친구)

3. 코드

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

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

max = sys.maxsize
D = [[max for _ in range(N+1)] for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    D[a][b] = 1
    D[b][a] = 1

for k in range(1, N+1):
    for s in range(1, N+1):
        for e in range(1, N+1):
            if D[s][e] > D[s][k] + D[k][e]: #D[x][y]에서 x가 출발노드, y가 도착노드
                D[s][e] = D[s][k] + D[k][e] #K를 경유해서 가는 게 더 짧을 경우 업데이트

bacon = [0]*(N+1)

for i in range(1, N+1):
    #i 친구의 베이컨 총합 구하기
    for j in range(1, N+1):
        if i!=j: #자기 자신은 무시하기
            bacon[i] += D[i][j]

bacon[0] = max
print(bacon.index(min(bacon)))

4. 코드 후기

• 플로이드 워셜 알고리즘 적용 문제의 공통점은 다른 노드를 경유하는 게 중요한 경우에 많이 사용된다는 점! 다른 노드를 거치는 걸 기준으로 문제 풀이를 할경우 플로이드-워셜 알고리즘을 기억해 적용하자!
• 플로이드-워셜 알고리즘 적용 문제는 결국 인접리스트를 어떻게 설정 할건지가 중요함!
  항상 최소가 되는 경로로 업데이트 해야 되니까 연결되지 않은 노드의 인접리스트 값이 INF인건 변함이 없을 것 같다! (아마도)