[Baekjoon] 11403: 경로 찾기 - (C3, S1) BFS

문제
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

11403번: 경로 찾기

 

가중치가 없는 그래프이므로, BFS 알고리즘을 사용한다. DFS 알고리즘도 경로가 존재하는지 여부를 확인할 수 있지만, 정점 i에서 정점j까지 경로가 존재하는지를 파악해야 하므로, 레벨 단위로 탐색이 이루어지는 BFS 알고리즘이 적합하다. 

 

유의할 점은 방향 그래프이기 때문에, 모든 정점에 대해 BFS 탐색을 수행해야 한다. 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int s, const vector<vector<int>> &g, vector<vector<int>> &answer)
{
    int n = g.size();
    vector<bool> visited(n, false); // 각 정점마다 독립적인 방문 배열
    queue<int> q;

    q.push(s);
    visited[s] = true;

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

        for (int w = 0; w < n; w++)
        {
            if (g[v][w] == 1 && !visited[w])
            {
                visited[w] = true;
                answer[s][w] = 1; // s부터 w까지 경로가 존재
                q.push(w);
            }

            if (g[v][w] == 1 && w == s) // 경유하여 자기 자신으로 돌아온 경우
                answer[s][s] = 1;
        }
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<vector<int>> adjacency_matrix(N, vector<int>(N, 0));
    vector<vector<int>> answer(N, vector<int>(N, 0));

    for (vector<int> &row : adjacency_matrix)
        for (int &e : row)
            cin >> e;

    for (int i = 0; i < N; i++) // 모든 시작 정점에 대해 bfs
        bfs(i, adjacency_matrix, answer);

    for (const vector<int> &row : answer)
    {
        for (const int &e : row)
            cout << e << " ";
        cout << '\n';
    }

    return 0;
}