[C++] 송아지 찾기(BFS : 상태트리탐색)

📄문제

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

 

⬇️ 입력

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.

 

⬆️ 출력

점프의 최소횟수를 구한다.

 

📝 풀이

#include <iostream>
#include <queue>
using namespace std;

bool visited[10001];
int dist[10001];

// 주어진 조건에 맞게 배열을 선언
int d[3] = { 1, -1, 5 };

int main()
{
	int S, E;
	scanf_s("%d %d", &S, &E);

	queue<int> q;

	q.push(S);
	visited[S] = true;

	while (!q.empty())
	{
		int currentPos = q.front();
		q.pop();

		if (currentPos == E)
		{
			printf("%d", dist[currentPos]);
			break;
		}

		for (int i = 0; i < 3; ++i)
		{
			if (!visited[currentPos + d[i]])
			{
				visited[currentPos + d[i]] = true;
				dist[currentPos + d[i]] = dist[currentPos] + 1;
				q.push(currentPos + d[i]);
			}
		}
	}
}

• 이전 문제와 마찬가지로 각 노드에서 -1, 1, 5로 나가는 노드가 있다고 가정하고 문제를 해결합니다.
• 이미 방문한곳이라면, 다른 방법으로 이미 최단거리로 방문하였다고 가정할 수 있습니다.
• 현재 위치가 E라면, 정답을 출력하고 함수를 종료합니다.