너비 우선 탐색(Breadth-first search, BFS)

너비우선탐색(BFS)는 다음처럼 물결이 퍼지듯 가까운 경로 후보부터 탐색하는 방법이다

한쪽 길을 끝까지 먼저 탐색하는 깊이우선탐색(DFS)과 비교된다

이런걸 왜쓰냐면 

1 최단경로를 구할때, 목적지를 찾자마자 최단경로임이 보장되어 탐색을 종료할 수 있는 장점이 있어 DFS에 비해 빠른경우가 많고

2 보통 재귀를 통해 시스템스택을 사용하는 DFS에 비해 queue를 사용하기 때문에 스택오버플로에서 비교적 자유롭고 힙공간을 넓게 쓸 수 있어 좀 더 넓은 범위 탐색에 유리하다.

S에서 E로 최단경로를 참색하는 아래 예제를 보자

시간복잡도

DFS와 마찬가지로 BFS도 인접행렬로 구현하면 $O(V^2)$이고 인접리스트로 구현하면 $O(V+E)$인것 같다. 

조금 헷갈리는건 간선이 많아도 결국 V개 노드만 방문하는데 O(E)가 어디서 소모되는지?.. 어쨌든 visted 정도라도 체크하니까 그런것일까? ㅎ

경로찍기 & 람다(lambda)함수 사용

#include <bits/stdc++.h>
using namespace std;
int N, K, x, c, visit[100001], from[100001];
deque<int> seq;
int main(void) {
    fill(from, from + 100001, -1);
    scanf("%d%d", &N, &K);
    queue<int> qx, qc;     qx.push(N), qc.push(0);
    while (qx.size()) {
        x = qx.front(); qx.pop();
        c = qc.front(); qc.pop();
        if (x == K) {
            printf("%d\n", c); break;
        }
        auto enqueue = [&](int v) {
            if (v <= 100000 && v >= 0 && visit[v] == 0) 
                visit[v] = 1, qx.push(v), qc.push(c + 1), from[v] = x;
        };
        enqueue(2 * x);
        enqueue(x - 1);
        enqueue(x + 1);
    }
    for (int i = 0; i <= c; i++) seq.push_front(K), K = from[K]; 
    for (auto a : seq)printf("%d ", a); printf("\n");
    return 0;
 }

최단거리 뿐 아니라 그 경로도 찍고 싶다면 위처럼 글로벌하게 from배열을 하나 운용하면 된다.

람다함수 사용도 잘 봐두자. 위 코드는 이 문제에 대한 답안이기도 하다.