[백준] 11403번 경로 찾기 c++

모든 i -> j에 대해 bfs가 성공하는지 여부를 탐색한다.

 

i에서 j로 가는 경로를 구하는 것이기 때문에 i==j인 경우에는 바로 bfs를 성공한다고 생각했는데 아니였다.

예제 2번의 경우 i=1, j=1 인 경우 경로가 없다는 결과였기 때문이다.

따라서  i==j 경우에는 bfs를 시작할때 방문배열을 체크하지 않고 다시 돌아오는지를 확인하였다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n;
int result[100][100]={0,};
vector<int> a[100];

void bfs(int start_x, int end_x){
    queue<int> q;
    int v[100]={0,};

    q.push(start_x);

    while(!q.empty()){
        int x = q.front();
        q.pop();

        if(x == end_x && v[x]==1){
            result[start_x][end_x] = 1;
            return;
        }

        for (int i = 0; i < a[x].size(); i++){
            int dx = a[x][i];
            if(v[dx]==0){
                q.push(dx);
                v[dx] = 1;
            }
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++){
        for (int x,j = 0; j < n; j++){
            cin >> x;
            if(x==1)
                a[i].push_back(j);
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if(result[i][j]==0)
                bfs(i, j);
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}