백준 11403번: 경로 찾기

 

 문제 설명 

 

1. 가중치가 없는 그래프가 주어진다 

2. 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램 출력

 

ex)

3

0 1 0

0 0 1

1 0 0

일때  1에서 2로가는 경로가있고 2에서 3으로가는 경로가 있고 3에서 1로가는 경로가 있다는 뜻.

 

 알고리즘 

 

플로이드 와샬 알고리즘을 통해 쉽게 구현 하였다 .

 

 

 코드 

 

#include #include using namespace std; int main() { cin.tie(NULL); ios::sync_with_stdio(false); int N,map[101][101]; cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; } } //플로이드 와샬 알고리즘 for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (!map[i][j]) if (map[i][k] && map[k][j])map[i][j] = 1; } } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << map[i][j] << " "; } cout << endl; } }