케빈 베이컨의 6단계 법칙

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구히야하는 경우

다익스트라는 한 지점에서 다른 특정 지점까지의 최단 경로구하는 알고리즘

 

문제 보자마자 걍 다익스트라, 플로이드 어쩌구 알고리즘 사용해야지! 떠올렸는데... 구현을 못함

 

시도

플로이드 워셜 알고리즘 구현시 고려할 점이 "거쳐 가는 노드" 를 기준으로 구현하면 되는데, 거처가는 노드 k 를 for루프 맨 처음에 시작해서 계속 실패함

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

#인접행렬
data = [[5001] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            data[i][j] = 0

for _ in range(m):
    a, b = map(int, input().split())
    data[a-1][b-1], data[b-1][a-1] = 1, 1

#최단 길이 구하기
for i in range(n):
    for j in range(n):
        for k in range(n):
            data[i][j] = min(data[i][j], data[i][k] + data[k][j])

#row더해서 가장 작은 값인 사람이 케빈 베이컨의 수가 가장 적음
result = []
for elements in data:
    result.append(sum(elements))
print(result.index(min(result)) + 1)

 

예를 들어서 1 -> 4로 가는 최단 경로를 구하기 위해서 1 -> k, k -> 4로 갈 수 있는 모든 경우의 수를 구한 후 작은 값을 data[1][4]에 저장하는 식으로 풀었다.

근데 문제에서 주어진 입력값으로 하니까 답이 맞다. 제출했더니 실패

그래서 질문 게시판에서 반례 찾아봤는데 모두 정답과 동일한 출력으로 나옴.

 

실패 원인

GPT한테 물어보니까 k가 가장 마지막 루프에 위치해야한다고 했다.

k 노드를 거쳐서 갈 수 있는 모든 경우의 수 중에서 최소값으로 1 -> (모든 노드)의 최소값 저장하고, 그다음으로 2 ->(모든노드) 최소값 저장하고... 이렇게

 

프롤이드 워셜 알고리즘의 핵심 개념은 모든 노드 쌍 사이의 최단 경로를 중간 노드(k)를 이용해 점진적으로 계산하는 방식이다.

K를 이용하여 다른 모든 노드 쌍 i, j간의 최단 거리를 갱신해야한다.

 

중간 노드를 중심으로 계산해야하는 이유

i, j, k 순서로 작성하면 k를 사용해서 거리를 갱신하기 전에 i와 j사이의 경로가 충분히 고려되지 않는다.

 

반례

k가 안쪽에 있는 경우 0->2으로 가는 최단 경로가 0->1->2인데,

k가 바깥에 있어서 k를 중심으로 값을 갱신하면 0->4->2같은 경로가 더 짧다는 사실을 갱신하지 못함.

 

1. data[0][0] + data[0][0]

2. data[0][1] + data[1][0]

3. data[0][2] + data[2][0]

4. data[0][3] + data[3][0]

5. data[0][4] + data[4][0]

 

루프가 끝나고 나면  data[0][0]에 대한 갱신은 더 이상 일어나지 않는다

따라서 중간 노드를 중심으로 먼저 모든 노드들에 대한 모든 지점까지의 최소값을 구해야한다

 

정답 코드

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

#인접행렬
data = [[(5001)] *(n) for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            data[i][j] = 0

for _ in range(m):
    a, b = map(int, input().split())
    data[a-1][b-1], data[b-1][a-1] = 1, 1

#최단 길이 구하기
for k in range(n):
    for i in range(n):
        for j in range(n):
            data[i][j] = min(data[i][j], data[i][k] + data[k][j])

#row더해서 가장 작은 값인 사람이 케빈 베이컨의 수가 가장 적음
result = []
for elements in data:
    result.append(sum(elements))
print(result.index(min(result)) + 1)