[11403] 경로찾기

문제 출처 : https://www.acmicpc.net/problem/11403

분류 : 그래프 백트래킹

백준 11403 경로찾기

각 정점간의 연결 여부를 확인하라

---

구현 포인트

1) 정점이 100개 밖에 안되므로 뭘 써도 제한시간 1초안에 가능하다.
(BFS, DFS, Flyod-Warshall)

2) 자기 자신간의 연결여부를 확인해야 한다. 자기 자신으로 돌아오는 싸이클의 여부 판단

정답률이 높고 쉬운 문제임에도 여기다 적는 이유는 처음에 2번을 고려하지 않았기에..ㅎㅎ;;;

구현된 코드는 아래와 같다. (BFS)

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    vector< vector<int> > adj(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> adj[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        queue<int> q;
        vector<bool> checked(N, false);
        q.push(i);
        while (q.size()) {
            int here = q.front();
            q.pop();
            for (int j = 0; j < N; j++) {
                if (adj[here][j] && !checked[j]) {
                    checked[j] = true;
                    q.push(j);
                }
            }
        }
        for (int j = 0; j < N; j++) {
            if (j != 0) cout << " ";
            cout << checked[j];
        }
        cout << '\n';
    }
}