문제 링크 : https://www.acmicpc.net/problem/11403
#include <iostream>
#include <algorithm>
using namespace std;
int N, via[101][101];
int main(){
//input
cin>>N;
for(int i=0; i<N;i ++)
{
for(int j=0; j<N; j++)
{
cin>>via[i][j];
}
}
//calc
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (via[i][k] == 1 && via[k][j] == 1) {
via[i][j] = 1;
}
}
}
}
//output
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<via[i][j]<<" ";
}
cout<<endl;
}
}
시간 복잡도가 |V|^3 인데 이게 최적인 것 같다.
플로이드 알고리즘 그대로 가져다 사용해도 되는데 이렇게 하는게 더 깔끔한듯 (사실 별 차이는 없다)
'알고리즘 > BOJ문제풀이' 카테고리의 다른 글
| 185번째 문제 - 9417 최대 gcd (0) | 2016.11.24 |
|---|---|
| 184번째 문제 - 1371 가장 많은 글자 (0) | 2016.11.24 |
| 미니 대회 (1) | 2016.11.23 |
| 183번째 문제 - 2667 단지번호붙이기 (0) | 2016.11.23 |
| 181번째 문제 - 1932 숫자삼각형 (0) | 2016.11.23 |