최소, 최단거리는 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