[ BOJ 백준 11403번 - 경로 찾기 ] 해설 및 코드

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

 

목적

모든 두 정점간의 경로가 존재하는지 구하자.

 

접근법

1. 플로이드 와샬 알고리즘으로 접근하자.

2. 알고리즘에 의해 i에서 j로 k를 거쳐갈 때, i와 k간의 경로가 존재하고 k와 j간의 경로가 존재하면 i와 j간의 경로가 존재하는 것이므로 값을 갱신한다.

 

#include<iostream>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,a[101][101];
    cin>>n;f(i,0,n)f(j,0,n)cin>>a[i][j];
    f(k,0,n)f(i,0,n)f(j,0,n)if(a[i][k]&&a[k][j])a[i][j]=1;
    f(i,0,n){
        f(j,0,n)cout<<a[i][j]<<' ';
        cout<<'\n';
    }
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.