[백준/그래프/C++] 11403번 경로 찾기

문제는 여기!

모든 정점에서 모든 정점으로의 최단 경로를 구하는 플로이드 와샬 알고리즘을 응용해서 푸는 문제이다

#include <bits/stdc++.h>

using namespace std;
int N;
int MAP[101][101];

void solve(){
    // i->j 로 가는 길이 없어도 k를 거쳐서 갈수있으면 갈수 있다고 여긴다
    for(int k=0; k<N; k++){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(MAP[i][k] && MAP[k][j])
                    MAP[i][j] = 1;
            }
        }
    }
}

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

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

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

    input();
    solve();
    printMap();

    return 0;
}