[BaekJoon/백준] 11403번 경로 찾기

 

digraph G에서,

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

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

 

 

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

문제가 인접행렬로 주어졌으므로, 곧바로 Floyd Warshall 알고리즘을 적용하기 좋은 환경이다.

 

// Directed Graph G가 주어지고
// transitive closure 찾는 것.

// Floyd Warshall 시간복잡도 : O(n^3)
// 또는 dfs를 n번 하는 방법도 있음.
// 인접 행렬로 주어졌으니 Floyd Warshall로.

#include <iostream>

using namespace std;

int N;
int Arr[100][100];

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> Arr[i][j];
        }
    }
    
    
    for(int i = 0; i < N; i++) {
        
            for(int j = 0; j < N; j++) {
                
                if(Arr[j][i] == 1) {
                    
                    for(int k = 0; k < N; k++) {
                        
                        if(Arr[i][k] == 1) {
                            
                            Arr[j][k] = 1;
                            
                        }
                    }
                    
                }
                
            }
                    
    }
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cout << Arr[i][j] << " ";
        }
        cout << "\n";
    }

    
}