[백준/c++] 11403 경로 찾기

✨ 문제 풀이

노드 i에서 노드 j까지 갈 수 있는 경로가 존재하는지 알아내는 문제이다. 즉 그 사이에 j, l, m ... 등 여러 개의 노드를 통해서 연결되어도 된다는 것이다. BFS를 통해서 연결되어 있는 노드들을 큐에 저장해서 탐색하면서 연결되어 있는지 저장해간다. 약간 다익스트라 알고리즘의 느낌도 난다.

여기서 중요한 것은 양방향 간선이 아니라 단방향 간선이라는 점! 따라서 사이클을 만들면서 자신으로 돌아오면 1이지만 사이클이 없으면 0이라는 것이다!!

 

나는 route라는 일차원 배열을 만들어서 한 노드가 다른 노드들과 연결 되어있는지 저장했다. route 배열을 0으로 초기화해주고, 방문하면 1을 저장한다. 이미 방문한 노드는 연결이 되어있다는 뜻이니 굳이 안 봐도 되고, 큐를 통해 방문하게 되는 노드는 1을 저장해준다. 그러면 자기 자신에게 사이클을 통해 돌아오는 경우도 정확하게 저장이 된다.

모든 노드에 대해서 반복해줘야 하므로 n 만큼 반복해주고 route 배열을 프린트해준다.

 

🗓 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<int> map[101];
int route[101];

void getInput()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            int isEdgeExists;
            cin >> isEdgeExists;
            if (isEdgeExists)
                map[i].push_back(j);
        }
}

void init()
{
    for (int i = 1; i <= n; i++)
        route[i] = 0;
}

void checkStartNodeAndOthersConnected(int start)
{
    init();

    queue<int> q;
    q.push(start);

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

        for (int next : map[current])
        {
            if (route[next])
                continue;
            route[next] = 1;
            q.push(next);
        }
    }
}

void printRoute() {
    for (int index = 1; index <= n; index++)
        printf("%d ", route[index]);
    printf("\n");
}

void printNodesConnection()
{
    for (int i = 1; i <= n; i++)
    {
        checkStartNodeAndOthersConnected(i);
    	printRoute();
    }
}

int main(void)
{
    getInput();
    printNodesConnection();
    return 0;
}