[백준] 11403 경로 찾기 Floyd Warshall

문제 : 

www.acmicpc.net/problem/11403

11403번: 경로 찾기

분석 :

이 문제는 플로이드 와샬 방식으로 접근해보았다.

백준 논의 보니까 DFS, BFS 로도 풀 수 있는 것 같아 보였다.

플로이드 와샬은 다익스트라 알고리즘과는 달리 모든 정점에서 모든 정점으로의 최단 경로를 찾는데 사용되는 알고리즘이다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택했다면 플로이드 와샬은 거쳐가는 정점을 기준으로 접근해야 한다는 점이 포인트였다. 

플로이드 와샬은 다이나믹 프로그래밍에 의거한다고 한다.

 

가장 이해되는 되목이라 하면은 X에서 Y로 가고 싶을 때

 

X에서 Y로 가는 최소 비용 VS X에서 1(거쳐가는 노드)로 가는 최소 비용 + 1에서 Y로 가는 최소 비용  

이었다.

 

그렇기 때문에 3개의 for문이 필요하고 거쳐가는 노드에 대해 시작 노드, 끝 노드 값을 변경시키며 모든 노드들을 검색한다.

 

c++ 코드 :

//
//  11403_path.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/18.
//

#include <stdio.h>
#include <iostream>

#define MAX 101
using namespace std;

int path[MAX][MAX];

void find_path(int n){
    int d[n][n];
    
    for(int i = 0; i< n; i++){
        for(int j = 0; j <n; j++){
            d[i][j] = path[i][j];
        }
    }
    
    //k 거쳐가는 노드
    for(int k = 0; k< n; k++){
        //i 출발 노드
        for(int i = 0; i <n; i++){
            //j 도착 노드
            for(int j = 0; j <n; j++){
                
                if(d[i][k] >0 && d[k][j] > 0){ //거쳐 가는 길 있으면
                    d[i][j] = 1;
                }
            }
        }
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << d[i][j] << " ";
        }
        cout << endl;
    }
    
    
    
    
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> path[i][j];
        }
    }
    
//    for(int i = 0; i< n; i++){
//        for(int j = 0; j <n; j++){
//            cout << path[i][j] << " ";
//        }
//        cout << endl;
//    }
    
    find_path(n);
    return 0;
}