[C++][백준 11403] 경로 찾기

[문제]

11403번: 경로 찾기 (acmicpc.net)

11403번: 경로 찾기

---

[문제 풀이]

플로이드-워셜 알고리즘을 통해서 풀어보도록 하자!

플로이드-워셜 알고리즘은 이전에 풀었던 플로이드 문제를 통해서 알아보도록 하자.

다만 플로이드 워셜의 경우에는 최소값을 찾지만 해당 문제에서는 경로가 있기만 하면 1로 바꾸도록 하자.

---

[코드]

#include <iostream>

using namespace std;

const int INF = 1000000;
int n;
int graph[101][101];

void floid(){
    for(int k = 0;k<n;k++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                if(graph[i][k] + graph[k][j] == 2){
                    graph[i][j] = 1;
                }
            }
        }
    }
}

int main(){
    cin>>n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin>>graph[i][j];
        }
    }
    
    floid();

    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cout<<graph[i][j]<<" ";
        }
        cout<<endl;
    }

    return 0;
}