[알고리즘] Floyd Warshall

digraph(방향이 있는 그래프) G에서,

 

A -> B로 가는 경로가 있고, B -> C로 가는 경로가 있다면

A -> C로 가는 경로도 존재한다는 Transitive closure를 계산하는 문제이다.

 

그래프 G에서 이러한 관계를 모두 연결해 준 그래프를 G* 이라고 부를 때, G*을 G의 transitive Clousre라고 한다. 

 

 

이는 dfs를 n번 적용하여 문제를 해결할 수도 있지만,

문제가 인접행렬로 주어질 경우, Floyd Warshall 알고리즘을 이용하여 Transitive Closure를 구하는 것이 구현이 쉽다.

 

    // i는 phase이다.
    // 총 N번의 phase가 있는 것이다.
    for(int i = 0; i < N; i++) {
        	// j는 아래로 쭉 내려가는 인덱스를 의미한다. 내려가면서 1을 찾는다.
            for(int j = 0; j < N; j++) {
                // 1을 찾았다면
                if(Arr[j][i] == 1) {
                    // 해당 phase에 맞는 행을 대상으로 1을 찾아내고, 값에 변화를 줌.
                    for(int k = 0; k < N; k++) {
                        
                        if(Arr[i][k] == 1) {
                            
                            Arr[j][k] = 1;
                            
                        }
                    }
                    
                }
                
            }
                    
    }

 

 

 

Floyd - Warshall 알고리즘 적용 문제

백준 11403번