[백준, 파이썬] 1389번 케빈 베이컨의 6단계 법칙

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

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

문제가 긴 관계로 링크로 올리겠습니다. 

요지는 결국 어떠한 그래프가 주어졌을 때 한 정점에서 다른 정점에 도달하기 위한

간선의 갯수들을 각각 구하고, 그것들을 모두 더하였을 때 그 값이 최소가 되는 '인싸' 정점이

무엇인지 찾아내는 문제입니다. 

 

즉 주어진 그래프에서 한정점에서 다른 정점으로 가는 모든 최단거리를 구해야 하는 문제로,

이러한 경우를 구하는 알고리즘을 '플로이드 와샬 알고리즘' 이라 합니다.

이 문제는 와샬 알고리즘만 알고있다면 5분안에도 풀 수 있을만큼 간단한 문제입니다.

 

예를 들어 다음과 같은 그래프가 있다고 가정합시다.

이 경우 현재 상태를 배열로 저장한다면 다음 두 가지 상태로 표현 가능합니다. 

거리를 저장한 테이블 D

직전 정점을 저장한 테이블 P

INF는 무한대를 의미하며, NIL은 직전 정점이 없다는 것을 의미합니다.

이제 이 그래프에서 모든 정점을 탐색하며 해당 정점을 중간 경로로 지정하면서 

해당 정점을 거쳐서 가는 경로와 기존의 경로중 최소값으로 그래프 값을 갱신합니다. 

 

즉 다음과 같이 테이블이 변화합니다. 

중간 경로 1을 추가한 테이블 D

 

중간 경로 1을 추가한 테이블 P

따라서 다음과 같은 알고리즘 수식을 구할 수 있습니다.

위 과정이 복잡해 보이긴하지만 결국 코드 한줄로 표현이 될 수 있습니다. 

import sys INF = sys.maxsize n, m= map(int, input().split(' ')) graph = [[INF for i in range(n)] for j in range(n)] result = [] def init(m): for i in range(n): for j in range(n): if i==j: graph[i][j] = 0 for k in range(m): //연결되어있는 정점들 값을 1로 초기화 i, j= map(int, input().split(' ')) graph[i-1][j-1]=1 graph[j-1][i-1]=1 def floyd_m(n): for k in range(n): for i in range(n): for j in range(n): if (graph[i][k] != INF and graph[k][j]!=INF): graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]) //플로이드 와샬 알고리즘, 값 갱신 def solve(n,m): init(m) floyd_m(n) for i in range(n): count = 0 for j in range(n): if i==j and graph[i][j]==INF: continue else: count += graph[i][j] result.append((i+1,count)) result.sort(key = lambda element:element[1]) print(result[0][0]) solve(n, m)