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

이 문제는 그래프에서 한 정점에서 다른 정점으로 가는 최단경로의 합이 가장 작은 정점을 구하는 문제입니다. dfs나 bfs로 해도 풀리겠지만, 처음 알게 된 폴로이드 와샬 알고리즘을 적용해보기 위해 저는 이 알고리즘을 사용했습니다.

폴로이드 와샬 알고리즘

정점 사이의 최단경로를 구할 때에 자주 사용하는 것이 다익스트라 알고리즘인데요. 다익스트라 알고리즘의 단점은 정점 사이의 가중치가 음수일 때 사용할 수 없다는 점입니다. 이에 반해 폴로이드 와샬 알고리즘은 가중치가 음수여도 사용이 가능합니다. 이름이 어렵게 생겨서 뭐지? 했는데 알고 보니 3중 포문을 이용해 모든 정점과 정점사이의 거리를 구하는 알고리즘이었습니다.

먼저 kebin이라는 int[][] 배열을 초기화하고, 주어진 정점들의 관게를 입력합니다. 그 다음, floyd() 함수에서 3중 포문을 돌며 각 정점과 정점사이의 최단경로를 갱신해줍니다. 이 때, k는 i 정점과 j 정점 사이의 거쳐가는 정점을 뜻합니다. 따라서 지금까지 구한 i에서 j로 가는 최단경로보다 i에서 k를 거쳐 j로 가는 경로가 더 짧다면 kebin[i][j] 의 값을 갱신하는 것입니다. 

코드