경로찾기

#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int n;
int map[101][101];
int ans[101][101];
bool d[101];
 
void bfs(int x){
    queue<int> q;
    int node = x;
    for(int i = 1; i<= n; i++){
        if(map[x][i]== 1 &&d[i] == false) {
            q.push(i);
            d[i] = true;
            ans[node][i] = 1;
        }
    }
    while(!q.empty()){
        x = q.front(); q.pop();
        for(int i = 1; i<= n; i++){
            if(map[x][i] == 1 && d[i] == false){
                d[i] = true;
                ans[node][i] = 1;
                q.push(i);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin>>map[i][j];
 
        }
    }
    for(int i = 1; i<= n; i++){
        bfs(i);
        memset(d,false, sizeof(d));
    }
    for(int i = 1; i<= n; i++){
        for(int j = 1; j<= n; j++)
        {
            cout<<ans[i][j]<<' ';
        }cout<<'\n';
    }
 
    return 0;
 
}

정말정말 쉬운 BFS문제였다.

일단 크기가 굉장히 작은 최대 100x100 배열이기때문에 초기화 등등 여러가지 부담될만한 시간적 요소가

없었기 때문에, 간단하게 짤수있었다.