BOJ11403 경로 찾기

선행지식

그래프 탐색 (플로이드-워셜 알고리즘)

문제

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

접근방식 1 (bfs)

m 에서 시작해서 갈 수 있는 모든 경로를 g배열에 기록한다.

#include <bits/stdc++.h>
using namespace std;
int a[101][101]={},g[101][101]={},n,m=0;
bool v[101]={};
queue<int> bfsq;
void search(int x){
    if(v[x]){
        g[m][x]=1;
        return;
    }
    v[x]=true;
    for(int i=0; i<n; i++){
        if(a[x][i]==1){
            g[x][i]=1;
            g[m][i]=1;
            bfsq.push(i);
        }
    }while (!bfsq.empty()){
        x=bfsq.front();
        bfsq.pop();
        search(x);
    }
    return;
}
int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> a[i][j];
        }
    }for(int i=0; i<n; i++){
        m=i;
        memset(v, false, 101*sizeof(bool));
        search(i);
    }for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << g[i][j] << ' ';
        }cout << '\n';
    }
}

태그에는 플로이드-워셜 알고리즘이 나오는데 이 알고리즘은 아직 잘 모른다.
나중에 알고리즘 복습하는 겸 다른 알고리즘과 정리해서 따로 올려야겠다.