<백준> 11403번 경로 찾기

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

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

문제 해결 과정: 

-플로이드 워셜 알고리즘 또는 bfs를 이용하여 풀 수 있다.

- a->b 정점간의 직접적인 연결과 a->c->b처럼 간접적인 연결이 있다.

- 세번의 반복문을 통하여 간접적인 연결또한 표시해준다.

#include<iostream>
 
using namespace std;
 
//플로이드 워셜 알고리즘, 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 구해준다.
 
int graph[101][101];
 
int main() {
    int N;
    scanf_s("%d", &N);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf_s("%d", &graph[i][j]);
        }
    }
 
    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]) {
                    graph[i][j] = 1;
                    cout << "graph[" << i << "]" << "[" << j << "]" << " = " << k << endl;
                }
            }
        }
 
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", graph[i][j]);
        }
        cout << endl;
    }
 
 
    return 0;
}