플로이드-워샬 알고리즘 (Floyd-Warshall Algorithm)

 

 

- 모든 정점에서 모든 정점까지의 최소 거리를 구한다.

 

- 다익스트라 알고리즘과 유사하나 다익스트라는 한 정점에서의 모든 정점과의 최소 거리를 구할 뿐이다.

 

- 다이나믹 프로그래밍이 적용된 알고리즘 이다.

 

- 정점끼리의 2차원 배열에서 [i][k] 가 연결되어 있고, [k][j]가 연결되어 있을 때, [i][k]가 연결되어 있음을 표시해준다.

 

- k를 첫번째 정점(1) 부터 정점의 수 n까지 반복한다.

 

 

예제) 프로그래머스 - 순위

 

https://programmers.co.kr/learn/courses/30/parts/14393

 

#include <string>
#include <vector>

using namespace std;

bool Node[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for(auto & i : results)
    {
        Node[i[0]][i[1]] = true;
    }
    
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(Node[i][k] && Node[k][j])
                    Node[i][j] = true;
            }
        }
    }
    
    int count;
    
    for(int i=1; i<=n; i++)
    {
        count = 0;
        for(int j=1; j<=n; j++)
        {
            if(Node[i][j] || Node[j][i])
                count++;
        }
        if (count == n-1)
            answer++;
    }
    return answer;
}