풀이 플로이드 와샬 알고리즘을 응용해야 하는 쉽지만은 않은 문제였던것 같다.숫자에 의미를 부여하여 그래프를 구성해야 하고, 이 의미를 부여하여 그래프를 완성하는 과정 자체가생각해내기 쉽지는 않았다. 문제 해결을 위한 생각의 과정은 다음과 같다.예를 들어 1 2 0 이라는 input이 주어지면 1에서 2로 가는 경로를 dis[1][2] 배열에 생성한다. 즉, 0이라는 값을 배열에 넣어준다는 것이다. 그리고 여기서 중요한 것이 2에서 1로 가는 경로가 없지만, 1에서 2로 가는 경로가 있기 때문에양방향의 경로가 연결될 가능성이 있으므로, 1이라는 값을 dis[2][1]에 넣어준다. 다시말해서, 이미 단방향이든, 양방향이든 경로가 있으면 거기에는 도로를 추가할 일이 없으므로 0을 넣어주고단방향의 경로가 없지만..

풀이 플로이드 와샬 알고리즘을 조금만 응용할 수 있다면 쉽게 해결되는 문제이다.그래프의 가중치를 저장하는 dis 배열과 같이 동작하는 count배열을 추가하였다.이 count 배열은 dis 배열이 갱신될 때마다 중간에 얼마나 많은 정점들이 연결되는 지를 카운트하여 저장하는 배열이다. 예를들어1 - 2 를 연결하는 가중치를 나타내는 dis[1][2] 값이1 - 3 - 2로 갱신될 때 count[1][2]값이 count[1][3] + count[3][2] 값으로 갱신되는 것이다. 이렇게 모든 점에 대해서 플로이드 알고리즘을 한바퀴 돌고 나면, dis배열과 count배열이 갱신되게 되고각각의 count값을 i값에 대해 합을 낸 것을 구하면, 각 i 값에 따른 케빈 베이컨의 수가 나오게 된다. 정리하면, 배열 ..