[백준/BOJ] 백준 11403번 : 경로 찾기
2020. 8. 11. 05:12ㆍ알고리즘 문제풀이
https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
플로이드 알고리즘을 이용하여 i에서 j로 가는 경로가 있는지 구한다
코드
#include <iostream>
using namespace std;
int n;
int adj[100][100];
//플로이드 알고리즘을 이용하여 i에서 j로 가는 경로가 있는지 구한다
void Solve()
{
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]);
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int temp;
cin >> n;
for(int i=0; i<n; i++)
for (int j = 0; j < n; j++)
{
cin >> temp;
adj[i][j] = temp;
}
Solve();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << adj[i][j] << " ";
}
cout << "\n";
}
return 0;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준/BOJ] 백준 1707번 : 이분 그래프 (0) | 2020.08.11 |
---|---|
[백준/BOJ] 백준 2583번 : 영역 구하기 (0) | 2020.08.11 |
[백준/BOJ] 백준 1987번 : 알파벳 (0) | 2020.08.11 |
[백준/BOJ] 백준 2668번 : 숫자고르기 (0) | 2020.08.11 |
[백준/BOJ] 백준 5014번 : 스타트링크 (0) | 2020.08.11 |