백준 11403 경로 찾기

이번에 풀어본 문제는 경로 찾기라는 문제이다.
문제 링크: https://www.acmicpc.net/problem/11403
해당문제는 정점의 수가 100으로 매우작고, 모든 노드로 부터 모든 노드로 가는 길이 존재하는지 유무를 알려주어야 하는 문제이다.

문제해결 알고리즘: 플로이드-워셜 알고리즘
이렇게 푼 이유? 위에 적은것 처럼 n의 수가 매우작고,(왜냐? 플로이드-워셜 알고리즘은 시간 복잡도가 O(N^3)이기 때문에 노드의 수가 적지 않으면 시간초과가 나게 된다...
또한 모든 노드가 시작점이 될수 있고, 모든 노드에 대해 최소값으로 도착할 수 있는 거리를 구할 수 있는것이 플로이드-워셜 알고리즘이기 때문에, 플로이드-워셜로 해당문제를 풀었다.
(+플로이드-워셜 알고리즘에 대해 추후 포스팅 할 예정이다.)

보통 플로이드 워셜 문제를 풀때, 이차원 배열을 선언해 행을 시작노드라 하면 열을 도착 노드로 설정해 그 배열의 값에 행->열로 향하기 위해 필요한 가중치를 저장하곤 한다.
이것을 활용했지만, 조금 다르게 푼 것은 이 문제에서는 행->열로 가는 간선이 존재하냐? 에 대해 존재하면 해당 배열 값이 1 없으면 0으로 출력되어야 하기 때문에, 행->열로 가는 간선이 없을 경우 INF로 각 배열을 초기화 해주었다.
나머지에 대한 것은 코드의 주석을 참고하면 될거 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1000000
using namespace std;

int graph[101][101];

int main(){
    
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    
    int n;
    
    //입력
    cin>>n;
    
    //처음 배열의 값 INF로 초기화
    for(int i=1;i<=n;i++){
        fill(graph[i], graph[i]+101,INF );
    }
    
    //만약 i->j로 가는 간선이 없는 경우 INF로 초기화
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>graph[i][j];
            if(graph[i][j]==0){
                graph[i][j]=INF;
            }
        }
        
        
    }
    
    //3중 for문으로 K를 경유해 i->j로 가는 값과 비교한다.
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
    
    //갈수 있는 간선이 존재할 경우 해당 배열의 값이 INF가 아니고
    //갈수 있는 간선이 존재하지 않을 경우 해당 배열의 값이 INF일 것 이다.
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(graph[i][j]!=INF){
                cout<<1<<" ";
            }
            else{
                cout<<0<<" ";
            }
            
        }
        cout<<"\n";
    }
    
    
    
    return 0;
}