백준, BOJ, 11403번, 경로 찾기 : C++ [CPP] ★★★★

플로이드 알고리즘으로 해결했다.

플로이드를 조금 더 풀어봐야겠다.

https://www.acmicpc.net/problem/11403

 

 

---

#맞는 풀이

#include <iostream>

#define MAX 101

using namespace std;

int N;

int adj[MAX][MAX];

void floyd()
{
    //i -> j는 바로 안가도 다른 노드를 거쳐서 가도 된다.
    //i -> k -> j 가능
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                if (adj[i][k] && adj[k][j])
                    adj[i][j] = 1; //인접행렬 자체를 바꿈 -> 해당 행렬은 i노드에서 j노드로 갈 수 있는지 여부를 저장하는 테이블이 됨
    return;
}




int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> adj[i][j]; //방향 그래프임.
        }
    }
    floyd();

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << adj[i][j] << " ";
        }
        cout << '\n';
    }



    return 0;
}

 

사실 플로이드 알고리즘도 최단거리를 알려주는 알고리즘이다.

여기서는 경로가 존재하는지만 알아봤기 때문이고 다른 문제를 풀어보면서 알아보자