백준 11403번: 경로 찾기

문제

문제 바로가기> 백준 11403번: 경로 찾기

풀이

플로이드-와샬 알고리즘을 이용하여 임의의 경로를 거쳐서라도 정점 i에서 j로 가는 간선이 존재한다면 그 값을 1로 변경해주었다.

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int path[101][101];
    int n; cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) cin >> path[i][j];
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(!path[i][j] && path[i][k] && path[k][j]) path[i][j] = 1;
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) cout << path[i][j] << ' ';
        cout << '\n';
    }
}