[BOJ] 11403. 경로 찾기 (C++)

문제

가중치 없는 방향 그래프가 주어졌을 때, 모든 정점에 대해서, 길이가 양수인 경로가 있는지 없는지 구하기

경로 있으면 1, 없으면 0 출력

생각할 것

모든 정점에 대해 모든 정점으로 간다는 것에서 바로 플로이드 와샬 선택!

코드

#include <iostream>
#include <vector>

#define INF 1e9

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N; // 가중치 없는 방향 그래프가 주어짐, 모든 정점에 대해 모든 정점으로 -> 플로이드 와샬
    cin >> N;

    int input;
    vector<vector<int>> adj(N, vector<int>(N, INF));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> input;
            if (input == 1) adj[i][j] = 1;
        }
    }

    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(adj[i][j] == INF) cout << 0 << " ";
            else cout << 1 << " ";
        }
        cout << "\\n";
    }

    return 0;
}