알고리즘 수업 - 너비 우선 탐색 1 (BFS)

https://www.acmicpc.net/problem/24444

24444번: 알고리즘 수업 - 너비 우선 탐색 1

* BFS 는 큐로 푼다. 

완전 기본문제니까 이걸로 먼저 이론을 생각하면서 풀면 될거같다. ! 그리고 sort는 compare 함수를 써서 이용해버릇 하자. 

+ cin/ cout 쓰면 시간초과구만.... 그냥 scanf / printf 로 쓰자. 

 

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

using namespace std;
#define MAX 100001

vector<int> graph[MAX];
int visited[MAX] = {0,};
int result[MAX] = {0,};
int cnt = 0;

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

void bfs(int r) {
    queue<int> qq;
    qq.push(r);
    visited[r] = 1;
    cnt++;
    result[r] = cnt;
    while(!qq.empty()) {
        int tmp = qq.front();
        qq.pop();
        for(int i = 0; i < graph[tmp].size(); i++) {
            int ttmp = graph[tmp][i];
            if(!visited[ttmp]) {
                visited[ttmp] = 1;
                cnt++;
                result[ttmp] = cnt;
                qq.push(ttmp);
            }
        }
    }
}

int main() {
    int n, m, r;
    scanf("%d %d %d", &n, &m, &r);
    for(int i = 1; i <=m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1; i <=n; i++) {
        sort(graph[i].begin(), graph[i].end(), compare);
    }
    bfs(r);
    for(int i = 1; i <= n; i++) {
        printf("%d\n", result[i]);
    }
    
    return 0;
}

여기서 그냥 deque를 써줘도 된다. 대신 push/pop에 front, back 을 적절히 넣어서 사용하면 된다.