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

bfs를 이용한 문제이다.

 

앞에서 풀었던 dfs와 같은 문제지만 bfs로 응용을 살짝 하면 손쉽게 풀 수 있다.

재귀함수로 인한 메모리 오류를 걱정안해도 좋다..ㅎ

 

□ 소스 코드

#include <bits/stdc++.h>

int bfsN,bfsM,bfsR;
vector<int> bfsList1[100001];
bool bfsVisited[100001];
queue<int> bfsQueue;
int* bfsRes;

void bfs24444(int v){
    int bfsCnt = 1;
    bfsVisited[v] = true;
    bfsRes[v] = bfsCnt;
    bfsQueue.push(v);
    
    while(!bfsQueue.empty()){
        int front = bfsQueue.front();
        bfsQueue.pop();
        
        for(int i=0;i<(int)bfsList1[front].size();i++){
            int next = bfsList1[front][i];
            if(!bfsVisited[next]){
                bfsQueue.push(next);
                bfsVisited[next] = true;
                bfsCnt++;
                bfsRes[next] = bfsCnt;
            }
        }
    }
}

bool bfsCompare(int a, int b){
    return a<b;
}

void BFS1(){
    scanf("%d%d%d",&bfsN,&bfsM,&bfsR);
    
    bfsRes = new int[bfsN + 1];
    
    for(int i=0;i<bfsM;i++){
        int bin1,bin2;
        scanf("%d%d",&bin1,&bin2);
        
        bfsList1[bin1].push_back(bin2);
        bfsList1[bin2].push_back(bin1);
    }
    
    for(int i=1;i<=bfsN;i++){
        sort(bfsList1[i].begin(),bfsList1[i].end(),bfsCompare);
    }
    
    bfs24444(bfsR);
    
    for(int i=1;i<=bfsN;i++)
        printf("%1d\n",bfsRes[i]);
}