백준 - 1389번 케빈 베이컨의 6단계 법칙 문제풀이 [Hellfer]

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

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

🔷 알고리즘 분류 - 너비 우선 탐색, 플로이드 - 워셜

난이도 - 실버 1

플로이드-워셜 알고리즘은 그래프에서 모든 노드 간의 최단 거리를 찾는 알고리즘입니다. 

 

이 알고리즘은 가중치가 있는 방향 그래프와 가중치가 있는 무방향 그래프에서 모두 사용할 수 있습니다. 

 

또한 음의 가중치를 갖는 간선이 있어도 적용할 수 있지만, 음의 사이클이 있으면 안 됩니다.

플로이드-워셜 알고리즘은 다이내믹 프로그래밍 기법을 이용합니다. 

 

이 알고리즘은 그래프의 각 노드를 한 번에 하나씩 거쳐 가는 경우를 고려하여 최단 거리를 계산합니다. 

 

이때, 한 노드를 거쳐 가는 모든 경우를 고려하므로 모든 노드 간의 최단 거리를 찾을 수 있습니다.

플로이드-워셜 알고리즘의 시간 복잡도는 O(N^3)으로, 노드의 개수가 N일 때 N^3의 연산이 필요합니다. 

 

따라서 노드의 개수가 많지 않은 그래프에서 이 알고리즘을 사용하는 것이 적절합니다.

플로이드-워셜 알고리즘은 다음과 같은 순서로 진행합니다:

1. 먼저 모든 노드의 거리를 '무한대'로 초기화하고, 자기 자신으로의 거리는 0으로 설정합니다.

2. 그래프의 간선 정보를 이용하여 노드 간의 거리를 갱신합니다.

3. 모든 노드를 한 번에 하나씩 거쳐 가는 경우를 고려하여 최단 거리를 갱신합니다.

 

이때, i에서 j로 가는 거리가 i에서 k를 거쳐 j로 가는 거리보다 크다면 i에서 j로 가는 거리를 i에서 k를 거쳐 j로 가는 거리로 갱신합니다.

 

이 과정을 모든 노드에 대해 반복합니다.

🔶문제 풀이 - 플로이드 워셜을 이용한 풀이

import sys
INF=float('inf')  # 무한대 값을 정의합니다.

n,m=map(int,input().split())  # n과 m을 입력받습니다. n은 사용자의 수, m은 친구 관계의 수를 나타냅니다.

graph=[[INF]*(n+1) for _ in range(n+1)]  # n+1 크기의 2차원 리스트를 생성하고, 모든 값을 무한대로 초기화합니다. 
        
for _ in range(m):  # m개의 친구 관계를 입력받습니다.
    x,y=map(int,input().split())  # 친구 관계인 두 사람 x와 y를 입력받습니다.
    graph[x][y]=1  # x와 y가 친구라면 거리를 1로 설정합니다.
    graph[y][x]=1  # y와 x가 친구라면 거리를 1로 설정합니다.
    
for i in range(1,n+1):  # 각 사람에 대해
    graph[i][i]=0  # 자기 자신과의 거리는 0으로 설정합니다.
    
for k in range(1,n+1):  # 모든 사람에 대해
    for i in range(1,n+1):  # 다른 모든 사람에 대해
        for j in range(1,n+1):  # 그 외의 다른 모든 사람에 대해
            graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j])  # i에서 j로 가는 거리와 i에서 k를 거쳐 j로 가는 거리를 비교하여 더 작은 값을 선택합니다.
                                                                 # 이렇게 하면 모든 노드 쌍의 최소 거리를 찾을 수 있습니다.
            
result=[0]*(n+1)  # 각 사람의 케빈 베이컨 수를 저장할 리스트를 생성합니다.

for i in range(1,n+1):  # 각 사람에 대해
    for j in range(1,n+1):  # 다른 모든 사람에 대해
        result[i]+=graph[i][j]  # i에서 j로 가는 최소 거리(케빈 베이컨 수)를 더합니다.
        
print(result.index(min(result[1:])))  # 케빈 베이컨 수가 가장 작은 사람의 번호를 출력합니다.

🔶문제 이해하기

print(result.index(min(result[1:])))

 

print(result.index(min(result [1:]))) 코드는 리스트 result에서 가장 작은 값을 가지는 요소의 인덱스를 출력하는 코드입니다.

min(result [1:]) 부분은 result 리스트의 첫 번째 요소를 제외하고(minimum을 찾을 때 0번째 요소를 무시하고 나머지에서 찾기 위해) 가장 작은 값을 찾습니다. 

 

이때, result 리스트의 각 요소는 해당 인덱스를 가지는 노드로부터 다른 모든 노드까지의 최단 거리의 합을 의미합니다. 

 

따라서 min(result [1:])는 모든 노드 중에서 다른 모든 노드까지의 최단 거리의 합이 가장 작은 노드를 찾는 것과 같습니다.

그리고 result.index(min(result [1:]))는 result 리스트에서 min(result [1:]) 값을 가지는 요소의 인덱스를 찾습니다. 

 

이 인덱스는 '케빈 베이컨의 6단계 법칙'에 따라 다른 모든 사람들과 가장 가까운 사람, 즉 '케빈 베이컨 수'가 가장 작은 사람의 번호를 의미합니다.

따라서 print(result.index(min(result [1:]))) 코드를 실행하면 '케빈 베이컨 수'가 가장 작은 사람의 번호가 출력됩니다.

 

만약 result 리스트가 [0, 4, 2, 3]라고 가정해 봅시다. 

 

이 리스트에서 첫 번째 요소(0번째 인덱스)는 사용하지 않는 값이므로 무시하고, 나머지 요소들 중에서 최솟값을 찾습니다.

min(result [1:]) 코드를 실행하면 result 리스트의 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 찾습니다. 

 

이 경우, 4, 2, 3 중에서 가장 작은 값은 2입니다.

그런 다음 result.index(min(result [1:])) 코드를 실행하여 result 리스트에서 2라는 값을 가지는 요소의 인덱스를 찾습니다. 

 

이 경우, 2라는 값을 가지는 요소의 인덱스는 2입니다.