[C++] 백준 BOJ 11403 경로 찾기

문제링크 : https://noj.am/11403

전형적인 BFS / DFS 문제

그냥 풀면 된다.

자기 자신노드로 돌아오는 경우가 있기 때문에 맨 처음은 방문체크를 하지 않았다.

인접리스트는 graph[0] = {1, 3, 5, 6, 7} 이런 형태로 저장된다. 현재 노드에서 해당 노드로 갈 수 있으면 저장된다.

// BOJ 11403 경로 찾기
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
    vector<vector<int> > graph(num); // 인접리스트
 
    int input;
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            cin >> input;
            if (input)
                graph[i].push_back(j);
        }
    }
 
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            vector<bool> visited(num, false);
            queue<int> Q;
            bool flag = false;
            for(int g : graph[i])
                Q.push(g);
            while(!Q.empty()){
                int cur = Q.front();
                Q.pop();
                visited[cur] = true;
                if(cur == j){
                    flag = true;
                    cout << 1 << " ";
                    break;
                }
                for(int g : graph[cur])
                    if(!visited[g])
                        Q.push(g);
            }
            if(!flag)
                cout << 0 << " ";
        }
        cout << "\n";
    }
    return 0;
}