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

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

풀이

정점 i에서 갈 수 있는 모든 정점을 구하면, 정점 i에서 정점 j로 갈 수 있는지를 출력할 수 있다.

1. 정점 i에서 간선으로 연결된 정점들을 graph[i]에 저장한다.
2. 정점 i에서 BFS를 통해 방문한 정점들을 visited 배열에 저장한다.
   큐의 front 요소를 cur라고 하고, cur에서 간선으로 연결된 정점들을 next라고 하면,
   next를 큐에 넣고, visited[next]를 1로 저장한다.
3. 정점 i에 대하여 visited 배열을 출력한다.
   visited[j]가 0이면 정점 i에서 j로 갈 수 없고, 1이면 갈 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N;
    cin >> N;

    vector<vector<int>> graph(N);
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            int x;
            cin >> x;
            if(x) graph[i].push_back(j);
        }
    }

    queue<int> q;
    for(int i=0; i<N; i++) {
        vector<bool> visited(N, false);
        q.push(i);

        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            
            for(int next : graph[cur]) {
                if(visited[next]) continue;
                q.push(next);
                visited[next] = true;
            }
        }

        for(int j=0; j<N; j++) {
            cout << visited[j] << " ";
        }
        cout << "\n";
    }

    return 0;
}