[백준] 11403번

floyd + bfs 개념을 이용

O(n*n*m)

m은 direct graph가 가르키는 갯수

#include <cstring>
#include <iostream>
#include <sstream>
#include <vector>

std::vector<std::vector<int>> graph;
std::ostringstream os;


void flyodBFS(int);

int main() {
    int n;
    std::cin >> n;
    graph.resize(n, std::vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> graph[i][j];
        }
    }
    flyodBFS(n);
    std::cout << os.str();
    return 0;
}

void flyodBFS(int n) {
    std::vector<int> visited(n);
    std::vector<int> path(n);
    std::vector<int> queue(n);
    for (int i = 0; i < n; i++) {
        std::memset(visited.data(), 0, sizeof(int) * n);
        std::memset(path.data(), 0, sizeof(int) * n);
        queue.clear();
        queue.push_back(i);
        while (!queue.empty()) {
            int _index = queue.front();
            path[_index] = 1;
            if (i == _index && !visited[_index]) {
                path[_index] = 0;
            }
            for (int j = 0; j < n; j++) {
                if (graph[_index][j] && !visited[j]) {
                    visited[j] = 1;
                    queue.push_back(j);
                }
            }
            queue.erase(queue.begin());
        }

        for (int j = 0; j < n; j++) {
            os << path[j] << " ";
        }
        os << std::endl;
    }

}