71. 송아지 찾기(BFS : 상태트리탐색) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <stdio.h>
#include <queue>

using namespace std;

queue<int> Q;
int dis[10001];
int dir[3] = {1, -1, 5};
int main()
{
	int s, e, x, val;
	scanf("%d %d", &s, &e);
	
	Q.push(s);
	
	while(!Q.empty())
	{
		val = Q.front();
		Q.pop();
		
		if(e - val >= 5) // 거리가 5이상 차이나면 5만큼 이동
		{
			dis[val + 5] = dis[val] + 1; // 다음 노드까지의 거리 = 지금까지 이동한 거리 + 1
			if(val + 5 == e) // 다음 노드가 목적지라면
			{
				printf("%d", dis[val + 5]);
				return 0;
			}
			Q.push(val + 5);
		}
		else // 그렇지 않다면 1, -1, 5 모두 이동해보기
		{
			for(int i = 0; i < 3; i++)
			{
				if(dis[val + dir[i]] == 0) // 한 번도 가보지 않은 노드라면
				{
					dis[val + dir[i]] = dis[val] + 1;
						if(val + dir[i] == e)
					{
						printf("%d", dis[val + dir[i]]);
						return 0;
					}
					Q.push(val + dir[i]);
				}
			}
		}
	}
	
	return 0;
}