알고리즘/문제풀이

11403 - 경로 찾기

이산한하루 2019. 5. 11. 23:58

인접행렬이 주어졌을 때 모든 정점 i, j 에 대하여 i에서 j로 가는 경로가 있는지 없는지 판단

For문으로 모든 정점의 추이관계를 찾아주면 된다.

#include <iostream>
#include <vector>
using namespace std;
int d[100][100];
int main() {
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> d[i][j];
        }
    }
    for (int k=0; k<n; k++) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (d[i][k] == 1 && d[k][j] == 1) {
                    d[i][j] = 1;
                }
            }
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}