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

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

사용 언어: C++

 

풀이

단순 BFS -> 큐에 넣어서 해당하는 애를 검사할땐 pop하면서 visited = true 해주고 다음 인접한 애를 visit 한 적 없으면 push하고 걔를 검사. 내림차순이므로 sort할때 greater<>() 넣기.

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

using namespace std;

vector<int> graph[100001];
int visited[100001];
int cnt = 1;

void bfs(int start)
{
    queue<int> q;
    q.push(start);
    visited[start] = cnt++;

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

        sort(graph[node].begin(), graph[node].end(), greater<>());

        for (int neighbor : graph[node])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = cnt++;
                q.push(neighbor);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M, R;
    cin >> N >> M >> R;

    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    bfs(R);

    for (int i = 1; i <= N; i++)
    {
        cout << visited[i] << "\n";
    }

    return 0;
}