[BOJ]1403-検索パス

💎 質問する
無重み付け方向図Gが与えられると、すべての頂点(i,j)に対してiからjへの経路があるか否かを決定するプログラムが作成される.
💎 入力
第1行は、頂点の個数N(1≦N≦100)を与える.2行目からN行目にかけてパターンの隣接行列が与えられる.i 1行目のj 1番目の数字が1の場合、iからjまでの幹線が存在し、0が存在しないことを示す.i 1行目のi 1番目の数字は常に0です.
ex)
3
0 1 0
0 0 1
1 0 0
💎 しゅつりょく
N行を共有し,問題の答えを隣接行列の形で出力する.頂点iからjへのパスがある場合は、i行目のj番号を1に出力する必要があります.そうしないと、出力は0になります.
ex)
1 1 1
1 1 1
1 1 1
💎 解答方法
問題の難易度はかなり容易であるが,後で出現するタイプのグラフィック探索である可能性もあるため,概念と理論を明らかにするために開発に発表した.問題を見るとグラフィックナビゲーションを利用した問題であることが分かるし、i行目のj個の数字を確認して更新することでdfsを利用してFloyd-Warshall(Floyd-Warshall)アルゴリズムを知ることもできるでしょう.
図には頂点の与えられた頂点と頂点との間の最短経路解の問題がしばしば現れ,floyd−とshallはすべての頂点からすべての頂点への最短経路を求めるアルゴリズムであると言える.隣接マトリクスでiからjまでのパスが存在する場合は、頂点に近い頂点を移動しながら、これらのパスを更新します!そこで、通過した頂点を基準に、繰り返し更新を行います!

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

前述したように、通過する頂点を基準として繰り返します.頂点mを基準として、iからjへのパスを決定した後、mを通過する位置であれば、i,jの位置のパスを1に更新する!それは遍歴する頂点の個数の繰り返しを通じて、隣接する行列の大きさの繰り返し文は解きます!
これは簡単な問題ですが、重み付けに関する問題が発生し、最小の重み付け値を更新し続ける可能性があるので、すべての頂点を基準に経路を探す必要がある場合はfloyd-washallを使いましょう.これに関連するアルゴリズムにはダエストラとベルマンフォードがあり、この2人も知っておく必要があります!
💎 完全なコード

#include <iostream>
#include <vector>
using namespace std;
int N;

int main(int argc, const char * argv[]) {
  
    cin >> N;
    vector <vector <int>> v(N + 1, vector<int>(N + 1));
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            cin >> v[i][j];
        }
    }
    
    for(int m = 0;m < N;m++){
        for(int i = 0;i < N;i++){
            for(int j = 0;j < N;j++){
                if(v[i][m] && v[m][j]){
                    v[i][j] = 1;
                }
            }
        }
    }
    
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            cout << v[i][j] << " " ;
        }
        cout << "\n";
    }
    
    return 0;
}

💎 悶える
今は休みまであと2週間ぐらい、、、時間が経つのが早いので、この時間を振り返ってみると、アルゴリズムを解いてvelogで発表して復習するように努力して、収穫の多い休暇です.残りの時間に練習を続け、プログラマースキルチェックも練習します.残りの時間の中で、私は解決したことがないタイプの問題や私のよく知らない問題を繰り返し解答して、それから記憶の深い問題をビデオにアップロードします!
がんばって!