백준[24445] 알고리즘 수업 - 너비 우선 탐색 2

앞에서 풀었던 bfs 문제에서 내림차순으로 변경되었다.

 

#include <bits/stdc++.h>

int bfsN2,bfsM2,bfsR2;
vector<int> bfsList2[100001];
bool bfsVisited2[100001];
queue<int> bfsQueue2;
int* bfsRes2;

void bfs24445(int v){
    int bCnt2 = 1;
    bfsVisited2[v] = true;
    bfsRes2[v] = bCnt2;
    bfsQueue2.push(v);
    
    
    while(!bfsQueue2.empty()){
        int front = bfsQueue2.front();
        bfsQueue2.pop();
        
        for(int i=0;i<bfsList2[front].size();i++){
            int next = bfsList2[front][i];
            if(!bfsVisited2[next]){
                bfsVisited2[next] = true;
                bfsQueue2.push(next);
                bCnt2++;
                bfsRes2[next] = bCnt2;
            }
        }
    }
}

bool bfsCompare2(int a, int b){
    return a>b;
}

void BFS2(){
    scanf("%d%d%d",&bfsN2,&bfsM2,&bfsR2);
    
    bfsRes2 = new int[bfsN2 + 1];
    
    for(int i=0;i<bfsM2;i++){
        int bin3,bin4;
        scanf("%d%d",&bin3,&bin4);
        bfsList2[bin3].push_back(bin4);
        bfsList2[bin4].push_back(bin3);
    }
    
    for(int i=1;i<=bfsN2;i++){
        sort(bfsList2[i].begin(),bfsList2[i].end(),bfsCompare2);
    }
    
    bfs24445(bfsR2);
    
    for(int i=1;i<=bfsN2;i++){
        printf("%d\n",bfsRes2[i]);
    }   
}