[C++] 백준 11403번 : 최단경로

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

 

문제

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

 

 

풀이

알고리즘 분류를 보니, 플로이드-워셜 문제로 되어있다.
이 알고리즘은 가중치가 음수도 처리할 수 있는 알고리즘이라고하는데,
가중치가 음수가 없는 이 문제가 왜 플로이드 워셜로 분류되었는지 모르겠다.

 

아무튼 이 문제는 각 노드를 돌면서, 해당 노드와 연결될 수 있는 다른 노드들이 있는 지 확인하기 위한 큐를 활용해 풀었다.

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

int board[101][101];
vector<vector<int>> graph(101);
int n;

void printer()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    // 입력받고
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int connected;
            cin >> connected;
            if (connected)
            {
                graph[i].push_back(j);
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        vector<bool> is_visited(n, false);
        queue<int> v;
        for (auto node : graph[i])
        {
            // 방문하지 않았고, 간선이 연결되어 있다면,
            board[i][node] = 1;

            v.push(node); // 시작 - 끝

            while (!v.empty())
            {
                auto target = v.front();
                // cout << "curr_node : " << i << " , " << target << endl;
                board[i][target] = 1;

                v.pop();

                if (is_visited[target] == false)
                {
                    is_visited[target] = true;
                    for (auto next_node : graph[target])
                    {
                        // cout << "next_node " << next_node << endl;
                        // 아직 방문하지 않은 노드라면면
                        if (is_visited[next_node] == false)
                        {
                            // cout << "push : " << next_node << " , " << endl;
                            v.push(next_node);
                        }
                    }
                }
            }
        }
    }
    printer();
}