[C++] BFS - 송아지 찾기

최소, 최단거리는 BFS가 유리하다

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

#define MAX 10001

using namespace std;

int main() { // 인접 리스트 안쓰고 푸는 방법임
    int S,E;
    
    queue<int> Q;
    
    scanf("%d %d",&S,&E);
    
    int dx[3] = {-1, 1, 5};//여러모로 굉장히 유용함
    
    int ch[MAX] ={0}; //distance를 가짐
    int x,i;
    int pos;
    
    
    ch[S] = 1;
    Q.push(S);
    
    while (!Q.empty()) {
        x = Q.front();
        Q.pop();
        for(i = 0; i < 3; i++){
            pos = x + dx[i];
            if(pos <= 0 || pos > 10000) continue;
            if(pos == E){
                printf("%d\n", ch[x]);
                exit(0);
            }
            if(ch[pos] == 0){
                ch[pos] = ch[x]+1;
                Q.push(pos);
            }
        }
    }
    
    return 0;
}

• DFS로도 물론 풀 수 있다.
• 하지만, 간단하게 예시를 들어보자면
• 사람이라면 송아지를 최소한으로 찾기 위해 한 가지 방법으로 일단 송아지까지 가볼 것이고, 그 다음 또 다른 방법으로 송아지까지 가볼 것이다. 이렇게 수많은 경우의 수를 각각 한 번씩 사용하여 송아지까지 가볼 것이다.(DFS)
• 하지만, BFS는 마치 사람이 분신술을 쓴 것처럼 세명이 동시에(물론 동시에는 아니고 queue순서대로 하지만) 정말 다양한 방법으로 송아지까지 찾아갈 것이다.(BFS)
• 이러한 비유만 봐도 당연히 BFS가 더 편리하다는 것을 알 수 있다. 특정 지점까지 가기 위한 최소한의 수를 찾겠다면 BFS가 더 유용하다는 것을 알 수 있다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard