[BOJ 24445] 알고리즘 수업 - 너비 우선 탐색 2 (C++)

알고리즘 수업 - 너비 우선 탐색 2 (Silver 2)

문제

전체 문제 보기

24445번: 알고리즘 수업 - 너비 우선 탐색 2

풀이

정점의 개수 N개만큼 정점을 만들고 각 정점에서 인접한 노드들을 먼저 방문하는 BFS를 구현하여서 푸는 문제. 다만, 인접한 노드를 방문할 때 인접한 노드 인덱스의 내림차순으로 방문해야 하기 때문에 인접한 노드 인덱스 값을 내림차순으로 정렬하는 단계가 필요함.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
struct Node {
    std::vector<int> adjacentIndex;
    int order{0};
};

void BFS(std::vector<Node>& Nodes, int R)
{
    std::queue<int> q;
    int order = 0;
    Nodes[R].order = ++order;
    q.push(R);

    while (!q.empty())
    {
        const int curNode = q.front();
        q.pop();
        for (int nextNode : Nodes[curNode].adjacentIndex)
        {
            if (Nodes[nextNode].order)
                continue;
            q.push(nextNode);
            Nodes[nextNode].order = ++order;
        }
    }
}

int main()
{
    //입출력 성능향상을 위한 설정
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);

    // 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)
    int N, M, R;

    std::cin >> N >> M >> R;
    std::vector<Node> Nodes(N + 1);

    for (int i = 0; i < M; ++i)
    {
        int a, b;
        std::cin >> a >> b;
        Nodes[a].adjacentIndex.push_back(b);
        Nodes[b].adjacentIndex.push_back(a);
    }
    for (int i = 1; i <= N; ++i)
    {
        std::sort(Nodes[i].adjacentIndex.begin(), Nodes[i].adjacentIndex.end(), [](int lhs, int rhs) {return lhs > rhs; });
    }

    BFS(Nodes, R);

    for (int i = 1; i <= N; ++i)
    {
        std::cout << Nodes[i].order << '\n';
    }

    return 0;
}