[BOJ/C++] 11403 경로 찾기

N이 최대 100이므로 플로이드-워셜 알고리즘을 이용해 문제를 해결할 수 있습니다.

기존 최단 경로를 찾는 문제가 아니라 모든 노드에 대해 갈 수 있는 경로가 있는지를 확인하는 문제로

$min(D[S][E], D[S][K] + D[K][E]$가 아닌 $D[S][K] == 1$ 이고 $D[K][E] == 1$ 이면 $D[S][E]$로 가는 경로가 존재합니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>

using namespace std;

using int32 = long;
using int64 = long long;


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

    int N;
    cin >> N;

    vector<vector<int>> G = vector<vector<int>>(N, vector<int>(N, 0));

    for(int i=0; i<N; i++)
    {
	    for(int j=0; j<N; j++)
            cin >> G[i][j];
    }

    // floyd

    for(int k=0; k<N; k++)
    {
	    for(int i=0; i<N; i++)
	    {
		    for(int j=0; j<N; j++)
		    {
                if (G[i][k] == 1 && G[k][j] == 1)
                    G[i][j] = 1;
		    }
	    }
    }

    for(int i=0; i<N; i++)
    {
        for (int j = 0; j < N; j++)
            cout << G[i][j] << ' ';
        cout << '\n';
    }


    return 0;
}