[12875] - 플로이드 머셜을 이용한 모든쌍의 최단경로 구하기

문제를 간단하게 정리하자면 친구관계로 묶여 있는 그래프가 있는데 그 그래프에서 모든쌍의 최단거리를 구하는 문제이다

그래프끼리의 간선의 가중치는 같다고 본다.  가중치가 다르다면 다익스트라 방식으로 접근해야 할 것이다.

플로이드 머셜에 대한 내용은 다음시간에 정리하는것으로 보고 이번시간에는 이 문제를 접근하는 방식에 대해서 먼저 생각해보도록 하자

그래프 내에서 각 간선들의 가중치는 같고 그 그래프 내에서의 모든쌍의 최단경로를 구하는 문제의 경우에는 플로이드 머셜 알고리즘을 사용하는데 알고리즘의 중요부분은 다음과 같다. 

for(int k=1;k<=num;k++){

        for(int i=1;i<=num;i++){

            for(int j=1;j<=num;j++){

                if(arr[i][j]>(arr[i][k]+arr[k][j])){

                    arr[i][j] = arr[i][k]+arr[k][j];

                }

            }

        }

    }

이게 핵심이다. 이렇게 for문을 돌게되면 돌면서 중복적으로 처리하는 작업없이 모든쌍의 최단경로들을 각각의 배열에 얻을 수 있다.

그런데 내가 맨처음에 생각했을때는 이런 for문을 만들 수 없었다. 왜냐하면 처음 배열을 선언할떄 연결이 되지 않아있는 경우를 0으로 초기화해주었기 때문인데 이러한 경우에는 초기값을들 10000으로 잡아주면 위와같은 플로이드 머셜을 쓸 수 있다.  그리고 자기자신의 경우 arr[i]i[]는 0 으로 초기화 해주어야 한다.